Longest Increasing Subsequence

Question

Given a sequence of integers, find the longest increasing subsequence (return length).

Example

I: [5, 4, 1, 2, 3]
O: len([1, 2, 3]) = 3
I: [4, 2, 4, 5, 3, 7]
O: len([2, 4, 5, 7]) = 4

Analysis

Implicit coordinate DP

Approach

1. Define (optimal) subproblem
LIS(i) = the max number of elements in the LIS at index i

2. Solve by prefix

for j from 0 to i-1
    LIS(i) = Math.max(LIS(i), LIS(j) + 1)

3. Init base
for i from 0 to n
    LIS(i) = 1

4. Topo order
for i from 0 to n

5. Final answer 
Note: because of the way we defined the subproblem, we need to find the max

for i from 0 to n
    answer = Math.max(answer, LIS(i))