Longest Increasing Subsequence Using Dynamic Programming

Formula:

array[j] < array[i] && dpArray[i] < dpArray[j] + 1

Algorithm:

1. Create an array of dpArray of same size
2. Populate dpArray with 1 at all places
3. Iterate i from 1 to array.length
   1. Iterate j from 0 to i
      1. If array[j] < array[i] && dpArray[i] < dpArray[j] + 1 then
         1. dpArray[i] = dpArray[j] + 1
4. Find max in dpArray
5. Return max

Latest Source Code:
Github: LongestIncreasingSubsequence.java

Output:

Array :[2, 7, 1, 3, 23, 2] LIS:3
Array :[1, 2, 3, 4, 23, 110] LIS:6
Array :[110, 12, 3, 2, 1] LIS:1