Given a sequence q of n numbers give an On 2 algorithm to f

Given a sequence q of n numbers, give an O(n 2 ) algorithm to find the longest monotone increasing subsequence in q. As always, prove the correctness of your algorithm and analyze its running time. Hint: Find a graph representation for this problem and use a graph algorithm (from class, lab or homework) to solve it.

Solution

For elegant display of solution visit
http://code.geeksforgeeks.org/hNZKdY
================================================================================
The Longest Increasing Subsequence (LIS) problem is to find the length of the longest
subsequence of a given sequence such that all elements of the subsequence are
sorted in increasing order. For example, the length of LIS for
{10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.
================================================================================================================
=>I will assume the indices of the array are from 0 to N - 1.
=>So let\'s define DP[i] to be the length of the LIS (Longest increasing subsequence)
which is ending at element with index i.
=>To compute DP[i] we look at all indices j < i and check both if DP[j] + 1 > DP[i] and array[j] < array[i]
(we want it to be increasing). If this is true we can update the current optimum for DP[i].
To find the global optimum for the array you can take the maximum value from DP[0...N - 1].
=>I use the array prev to be able later to find the actual sequence not only its length.
Just go back recursively from bestEnd in a loop using prev[bestEnd]. The -1 value is a sign to stop.
================================================================================================================

int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;

for (int i = 1; i < N; i++)
{
DP[i] = 1;
prev[i] = -1;

for (int j = i - 1; j >= 0; j--)
if (DP[j] + 1 > DP[i] && array[j] < array[i])
{
DP[i] = DP[j] + 1;
prev[i] = j;
}

if (DP[i] > maxLength)
{
bestEnd = i;
maxLength = DP[i];
}
}
===================================================================================
As we are using two for loops the inner for loop in worst case gets executed \'n\' times.
so, he time compleity is O(n^2)
================================================================================
For Graph representation of the problem visit:
//http://www.stoimen.com/blog/2012/12/03/computer-algorithms-longest-increasing-subsequence/