The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Dynamic Programming

Problem :-
Longest Increasing Subsequence ( LIS ) problem.
Given a sequence, find the length of longest subsequence such that all elements in the subsequence are
sorted in increasing order.
Consider the sequence { 9, 5, 2, 8, 7, 3, 1, 6, 4, 5 }
Length of Longest Increasing Subsequence ( LIS ) = 4 & the elements are { 2, 3, 4, 5 }

Solution :-
Suppose the input sequence is arr [ 0 ... n ].
We will maintain an input array lis [ n + 1 ] where lis [ i ] contains the length of LIS till index ' i ' such that
arr [ i ] is the last element of the LIS.
Eventually, maximum element in lis [ ] gives the length of LIS of the input array or sequence.
Let us find the structure of the optimal solution.
Let lis ( i ) denotes the Longest Increasing Subsequence ( LIS ) till index ' i ' of the input array arr [ 0 ... n ] such that arr [ i ] is the part of LIS.
Then, lis ( i ) = 1 + maximum [ lis ( j ) ] for all j < i and arr [ j ] < arr [ i ]
Finally, max ( lis [ 0 ... n ] ) gives the required solution.

#include<iostream>
using namespace std;

/* Find the length of longest increasing subsequence
   suppose n -> length of given sequence
   lis(i) -> LIS till the 'i' index of the given sequence
   lis(n) -> LIS of the sequence 
   Standard Recursive Solution :-
   lis(i) = 1 + max(lis(j) for all j < i and arr[j] < arr[i])     
*/
int findLIS(int arr[], int n) {
   // array to store lis values at each index
   // lis[i] -> LIS till 'i' index of the array
   int lis[n];
   int i, j, max = 0;

   // initialize lis values at all index  
   for (i=0;i<n;i++)
      lis[i] = 1;

   // Compute LIS values at each index 
   for (i=1;i<n;i++) {
      // as per the recursive solution
      // for all j < i and arr[j] < arr[i]
      for (j=0;j<i;j++) {
         if (arr[j] < arr[i]) {
            // we are looking for max value of lis(i), so update the value
            if (lis[i] < (lis[j] + 1)) {
               lis[i] = lis[j] + 1;
            }
         }
      }
   }

   // get the maximum of all values stored in lis array
   for (i=0;i<n;i++) {
      if (max < lis[i])
         max = lis[i];
   }

   return max;
}

// main
int main() {
   int arr[] = {9,5,2,8,7,3,1,6,4,5};
   int len = sizeof(arr)/sizeof(arr[0]);
   cout<<"\nLength of LIS :: "<<findLIS(arr,len);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Dynamic Programming
* Find the nth term of fibonacci series
* Evaluate combination(n, r)
* Solve the Edit-Distance problem
* Longest Common Subsequence ( LCS ) problem
* Given a set of coin denominations, find the minimum number of coins required to make a change for a target value
* Longest Increasing Subsequence ( LIS ) problem
* Unbounded Knapsack problem
* 0/1 Knapsack problem
* Splitting a string into minimum number of palindromes