### Longest Increasing Subsequence Using Dynamic Programming

##### Formula:

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

##### Algorithm:

- Create an array of dpArray of same size
- Populate dpArray with 1 at all places
- Iterate i from 1 to array.length
- Iterate j from 0 to i
- If
`array[j] < array[i] && dpArray[i] < dpArray[j] + 1`

then`dpArray[i] = dpArray[j] + 1`

- If

- Iterate j from 0 to i
- Find max in dpArray
- 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