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

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 arrayint 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 valueif (lis[i] < (lis[j] + 1)) {
lis[i] = lis[j] + 1;
}
}
}
}
// get the maximum of all values stored in lis arrayfor (i=0;i<n;i++) {
if (max < lis[i])
max = lis[i];
}
return max;
}
// mainint 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;
}

#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 arrayint 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 valueif (lis[i] < (lis[j] + 1)) {
lis[i] = lis[j] + 1;
}
}
}
}
// get the maximum of all values stored in lis arrayfor (i=0;i<n;i++) {
if (max < lis[i])
max = lis[i];
}
return max;
}
// mainint 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;
}