Longest Increasing Subsequence

Problem: Find length of the subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

Example : {10, 25, 9, 30, 21, 55, 40, 60, 75}
Here Length of LIS is 6 and LIS could be [10,25,30,40,60,75] and [10,25,30,55,60,75].

Algorithm : Let’s define L[i] to be the length of the LIS(Longest increasing subsequence) which is ending at element with index i. To compute L[i] we look at all indices j < i and check both if L[j] + 1 > L[i] and arr[j] < arr[i](we want it to be increasing). If this is true we can update the current optimum for L[i]. To find the global optimum for the array you can take the maximum value from L[0..N-1].

int LongestIncreasingSeq(int arr[],int N)
{
    int maxLength = 1;
    int L[N];
    L[0] = 1;

    for (int i = 1; i < N; i++)
    {
       L[i] = 1;

       for (int j=0; j<i; j++)
       {
          if (L[j] + 1 > L[i] && arr[j] < arr[i])
          {
             L[i] = L[j] + 1;
          }
       }
       if (L[i] > maxLength)
       {
          maxLength = L[i];
       }
    }
    return maxLength;
}

Time Complexity : O(N^2)