#### 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);
cout<<"\nLength of LIS :: "<<findLIS(arr,len);
cout<<endl;
return 0;
}```