9 lines
330 B
Plaintext
9 lines
330 B
Plaintext
Longest Increasing Subsequence: [10, 9, 2, 5, 3, 7, 101, 18]
|
|
============================================================
|
|
|
|
a[i] [10, 9, 2, 5, 3, 7, 101, 18]
|
|
dp[i] [1, 1, 1, 2, 2, 3, 4, 4] (dp[i] = longest increasing subsequence ENDING at index i)
|
|
|
|
answer = max(dp) = 4 (for example 2, 3, 7, 18)
|
|
O(n log n) patience version = 4
|