Longest Increasing Subsequence

One-dimensional DP with predecessor reconstruction

End each subproblem at a specific index

Let dp[i] be the length of the longest strictly increasing subsequence that ends at index i. Every value can stand alone, so all entries start at 1. To solve dp[i], inspect every earlier index j.

Extend only from a smaller value

If a[j] < a[i], an increasing subsequence ending at j can accept a[i]. Update dp[i] with dp[j] + 1 when it is larger, and remember j as the predecessor. The largest DP entry gives the global length.

The two-row matrix shows input values above their DP lengths. Yellow cells identify the value and predecessor under comparison, green marks an improvement, and the final highlighted value path follows predecessors back to one optimal sequence.

	0	1	2	3	4	5
Value	1	3	2	4	3	5
dp	1	1	1	1	1	1

Initialize every dp[i] to 1 because each value forms a length-one subsequence.

1function longestIncreasingSubseq(a: number[]): number[] {
const n = a.length;
const dp = new Array(n).fill(1);               // each element alone has length 1
const pred = new Array(n).fill(-1);
for (let i = 1; i < n; i++) {
  for (let j = 0; j < i; j++) {
    if (a[j] < a[i] && dp[j] + 1 > dp[i]) {    // can extend to a longer sequence
      dp[i] = dp[j] + 1;
      pred[i] = j;
    }
  }
}
let best = 0;
for (let i = 1; i < n; i++) if (dp[i] > dp[best]) best = i; // find the best ending position
const lis: number[] = [];
for (let k = best; k !== -1; k = pred[k]) lis.unshift(a[k]); // reconstruct through predecessors
return lis;
18}

Input1 3 2 4 3 5

dp1 1 1 1 1 1

1 / 18

The transparent quadratic solution

Comparing each pair with j < i takes O(n^2) time and O(n) space. A patience-sorting method with binary search reaches O(n log n), but this DP makes the ending-index state and reconstruction invariant explicit.

Invariant: after index i is processed, dp[i] is optimal among all increasing subsequences whose final value is a[i].

Compare one-sequence predecessor links with the two-string trace in Longest Common Subsequence.

Algorithm Visualizer

Longest Increasing Subsequence

End each subproblem at a specific index

Extend only from a smaller value

The transparent quadratic solution