Construction of Longest Monotonically Increasing Subsequence (N log N) | GeeksforGeeks

Construction of Longest Monotonically Increasing Subsequence (N log N) | GeeksforGeeks
Construction of Longest Monotonically Increasing Subsequence (N log N) | GeeksforGeeks

int LongestIncreasingSubsequence(int A[], int size) {

   // Add boundary case, when array size is zero

   // Depend on smart pointers

   int *tailIndices = new int[size];

   int *prevIndices = new int[size];

   int len;

   memset(tailIndices, 0, sizeof(tailIndices[0])*size);

   memset(prevIndices, 0xFF, sizeof(prevIndices[0])*size);

   tailIndices[0] = 0;

   prevIndices[0] = -1;

   len = 1; // it will always point to empty location

   for( int i = 1; i < size; i++ ) {

      if( A[i] < A[tailIndices[0]] ) {

         // new smallest value

         tailIndices[0] = i;

      } else if( A[i] > A[tailIndices[len-1]] ) {

         // A[i] wants to extend largest subsequence

         prevIndices[i] = tailIndices[len-1];

         tailIndices[len++] = i;

      } else {

         // A[i] wants to be a potential condidate of future subsequence

         // It will replace ceil value in tailIndices

        int pos = GetCeilIndex(A, tailIndices, -1, len-1, A[i]);

        prevIndices[i] = tailIndices[pos-1];

        tailIndices[pos] = i;

      }

   }

   cout << "LIS of given input" << endl;

   for( int i = tailIndices[len-1]; i >= 0; i = prevIndices[i] )

      cout << A[i] << "   ";

   cout << endl;

   delete[] tailIndices;

   delete[] prevIndices;

   return len;

}

http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

Java code at https://sites.google.com/site/indy256/algo/lis_nlogn
Also refer to http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
Longest Monotonically Increasing Subsequence Size (N log N) | GeeksforGeeks
http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming
1. You know Kadane‘s algorithm to find maximum sum sub-array. Modify Kadane’s algorithm to trace starting and ending location of maximum sum sub-array.
2. Modify Kadane‘s algorithm to find maximum sum sub-array in a circular array. Refer GFG forum for many comments on the question.
3. Given two integers A and B as input. Find number of Fibonacci numbers existing in between these two numbers (including A and B). For example, A = 3 and B = 18, there are 4 Fibonacci numbers in between {3, 5, 8, 13}. Do it in O(log K) time, where K is max(A, B). What is your observation?
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
Read full article from Construction of Longest Monotonically Increasing Subsequence (N log N) | GeeksforGeeks