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

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;

}

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