演算法

1function lisDp(a: number[]): number[] {
2  const n = a.length;
3  const dp = new Array(n).fill(1);
4  const prev = new Array(n).fill(-1);
5  for (let i = 0; i < n; i++) {
6    for (let j = 0; j < i; j++) {
7      if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
8        dp[i] = dp[j] + 1;
9        prev[i] = j;
10      }
11    }
12  }
13  let best = 0;
14  for (let i = 1; i < n; i++) if (dp[i] > dp[best]) best = i;
15  const out: number[] = [];
16  for (let k = n ? best : -1; k !== -1; k = prev[k]) out.push(a[k]);
17  out.reverse();
18  return out;
19}
20 
21function lisTails(a: number[]): number[] {
22  const tails: number[] = []; // index of the smallest ending per length
23  const parent = new Array(a.length).fill(-1);
24  for (let i = 0; i < a.length; i++) {
25    let lo = 0, hi = tails.length;
26    while (lo < hi) {
27      const mid = (lo + hi) >> 1;
28      if (a[tails[mid]] < a[i]) lo = mid + 1; else hi = mid;
29    }
30    parent[i] = lo > 0 ? tails[lo - 1] : -1;
31    if (lo === tails.length) tails.push(i);
32    else tails[lo] = i;
33  }
34  const out: number[] = [];
35  for (let k = tails.length ? tails[tails.length - 1] : -1; k !== -1; k = parent[k]) out.push(a[k]);
36  out.reverse();
37  return out;
38}