Dynamic Programming
DP State Tables
Watch tabulation fill one state at a time with dependencies, current result, and per-step time and space complexity.
O(n log n)
State a010
State a19
State a22
State a35
State a43
State a57
State a6101
State a718
Result
-
Time
O(n log n)
Space
O(n)
Step Note
Use binary search over tails for LIS length.
function lengthOfLIS(values: number[]) {
const tails = []
for (const value of values) {
let left = 0
let right = tails.length
while (left < right) {
const mid = Math.floor((left + right) / 2)
if (tails[mid] < value) left = mid + 1
else right = mid
}
tails[left] = value
}
return tails.length
}