Longest increasing subsequence

Find a longest strictly increasing sequence that preserves input order while allowing gaps.

Remember: Each state ends at one index.

Example: [3,1,2,5] → [1,2,5], length 3.

Time: O(n²). Auxiliary space: O(n).

Formula: dp[i] = 1 + max(dp[j]) over j < i with a[j] < a[i]; default 1

Up to 15 integers, duplicates allowed. Strictly increasing, not nondecreasing. Each state ends at a particular input index. Predecessors recover one optimal subsequence; empty input has length 0. This lesson uses quadratic DP, not the O(n log n) tails method.

Complexities describe the underlying algorithm; tutorial snapshots and rendering can use additional resources.

The interactive workspace loads here when JavaScript is available. You can still browse the learning notes and links above without it.