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

# Algorithms

## 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.