Dynamic Programming | Set 3 (Longest Increasing Subsequence) | GeeksforGeeks

Dynamic Programming | Set 3 (Longest Increasing Subsequence) | GeeksforGeeks
-- O(NlogN) Algorithm http://massivealgorithms.blogspot.com/2014/08/longest-monotonically-increasing.html
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, length of LIS for { 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and LIS is {10, 22, 33, 50, 60, 80}.

Optimal Substructure:
Let arr[0..n-1] be the input array and L(i) be the length of the LIS till index i such that arr[i] is part of LIS and arr[i] is the last element in LIS, then L(i) can be recursively written as.
L(i) = { 1 + Max ( L(j) ) } where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1
To get LIS of a given array, we need to return max(L(i)) where 0 < i < n
So the LIS problem has optimal substructure property as the main problem can be solved using solutions to subproblems.
Following is a tabluated implementation for the LIS problem.

int lis( int arr[], int n )

{

   int *lis, i, j, max = 0;

   lis = (int*) malloc ( sizeof( int ) * n );

   /* Initialize LIS values for all indexes */

   for ( i = 0; i < n; i++ )

      lis[i] = 1;

   /* Compute optimized LIS values in bottom up manner */

   for ( i = 1; i < n; i++ )

      for ( j = 0; j < i; j++ )

         if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)

            lis[i] = lis[j] + 1;

   /* Pick maximum of all LIS values */

   for ( i = 0; i < n; i++ )

      if ( max < lis[i] )

         max = lis[i];

   /* Free memory to avoid memory leak */

   free( lis );

   return max;

}

EPI Java Solution

Find the longest nondecreasing subsequence

LongestNondescreasingSubsequenceN2.java
-- O(N^2)
  public static List<Integer> longestNondecreasingSubsequence(List<Integer> A) {
    // Empty array.
    if (A.isEmpty()) {
      return A;
    }

    List<Integer> longest = new ArrayList<>(A.size());
    List<Integer> previousIndex = new ArrayList<>(A.size());
    for (Integer aA : A) {
      longest.add(1);
      previousIndex.add(-1);
    }

    int maxLengthIdx = 0;
    for (int i = 1; i < A.size(); ++i) {
      for (int j = 0; j < i; ++j) {
        if (A.get(i) >= A.get(j) && longest.get(j) + 1 > longest.get(i)) {
          longest.set(i, longest.get(j) + 1);
          previousIndex.set(i, j);
        }
      }
      // Records the index where longest subsequence ends.
      if (longest.get(i) > longest.get(maxLengthIdx)) {
        maxLengthIdx = i;
      }
    }

    // Builds the longest nondecreasing subsequence.
    int maxLength = longest.get(maxLengthIdx);
    List<Integer> ret = new ArrayList<>(maxLength);
    while (maxLength-- > 0) {
      ret.add(0, A.get(maxLengthIdx));
      maxLengthIdx = previousIndex.get(maxLengthIdx);
    }
    return ret;
  }
-- O(NLogN)
LongestNondescreasingSubsequenceNlogn.java
Following is simple recursive implementation of the LIS problem. 

int _lis( int arr[], int n, int *max_ref)

{

    /* Base case */

    if(n == 1)

        return 1;

    int res, max_ending_here = 1; // length of LIS ending with arr[n-1]

    /* Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2]. If

       arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs

       to be updated, then update it */

    for(int i = 1; i < n; i++)

    {

        res = _lis(arr, i, max_ref);

        if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)

            max_ending_here = res + 1;

    }

    // Compare max_ending_here with the overall max. And update the

    // overall max if needed

    if (*max_ref < max_ending_here)

       *max_ref = max_ending_here;

    // Return length of LIS ending with arr[n-1]

    return max_ending_here;

}

Read full article from Dynamic Programming | Set 3 (Longest Increasing Subsequence) | GeeksforGeeks