Longest Increasing Subsequence: O(n²) DP and O(n log n)

Given an array of numbers, pick as many as you can, keeping their original order, so that each one is larger than the one before. That selection is an increasing subsequence, and the longest one is the longest increasing subsequence, or LIS. In [5, 2, 8, 6, 3, 6, 9, 7, 1] you can pick 2, 3, 6 and 9, and no five values work, so the LIS has length 4. It is the hidden core of many interview questions, and the first dynamic programming problem whose answer is not in the last cell.

Why brute force and greedy both fail

A subsequence keeps the original order but may skip elements; a subarray is a contiguous block. An array of n elements has 2ⁿ subsequences, each element in or out, so trying them all is hopeless beyond about n = 25, and the usual limit here is n = 2,500. Neither a single scan nor a greedy rule finds it:

1. A subsequence keeps the original order but may skip elements. Picking indices 1, 4, 5 and 6 gives 2 < 3 < 6 < 9: an increasing subsequence of length 4, and no five values work.
2. A subarray may not skip anything. The longest increasing run is [3, 6, 9], length 3, and one left-to-right scan finds it. A subsequence has 2ⁿ choices instead, which is why it needs more than a scan.
3. Greedy takes each value that beats the last one taken: 5, 8, 9, length 3. Taking the 8 shut out the 6 and the 7 after it. Whether to take a value depends on what comes later.

The right choice at each element depends on the rest of the array. That is the signal for dynamic programming.

The O(n²) idea: the longest subsequence ending at each index

The state that works is narrower than the obvious one:

• State: dp[i] is the length of the longest increasing subsequence that ends exactly at index i.
• Transition: dp[i] = 1 + the largest dp[j] over every j < i with nums[j] < nums[i], or 1 if there is none.
• Answer: the largest dp[i] over all i, not dp[n − 1]. The LIS can end anywhere.

Why "ends at i"? To extend a subsequence you must know its last value; fixing where it ends puts that value in the state for free.

1. dp[i] is the length of the longest increasing subsequence that ends exactly at index i. Nothing comes before 5, and nothing before 2 is smaller, so dp[0] = dp[1] = 1: each value alone.
2. 8 can follow any earlier, smaller value: 5 and 2. The best dp among them is 1, first reached at index 0, so dp[2] = 1 + 1 = 2, and the arc records index 0 as the parent.
3. 6 can follow any earlier, smaller value: 5 and 2. The best dp among them is 1, first reached at index 0, so dp[3] = 1 + 1 = 2, and the arc records index 0 as the parent.
4. 3 can follow any earlier, smaller value: 2. The best dp among them is 1, at index 1, so dp[4] = 1 + 1 = 2, and the arc records index 1 as the parent.
5. 6 can follow any earlier, smaller value: 5, 2 and 3. The best dp among them is 2, at index 4, so dp[5] = 2 + 1 = 3, and the arc records index 4 as the parent. The earlier 6 is equal, not smaller, so it cannot come first.
6. 9 can follow any earlier, smaller value: 5, 2, 8, 6, 3 and 6. The best dp among them is 3, at index 5, so dp[6] = 3 + 1 = 4, and the arc records index 5 as the parent.
7. 7 can follow any earlier, smaller value: 5, 2, 6, 3 and 6. The best dp among them is 3, at index 5, so dp[7] = 3 + 1 = 4, and the arc records index 5 as the parent.
8. Nothing before 1 is smaller, so it starts a subsequence of its own: dp[8] = 1. It is the last cell, but nowhere near the answer — the longest can end anywhere.
9. The answer is the largest dp, 4 at index 6. Following the parent arcs back gives indices 6 → 5 → 4 → 1, values 9, 6, 3, 2; reversed, the LIS is 2, 3, 6, 9.

Why it works

Take any increasing subsequence that ends at index i. Either it is nums[i] alone, or its second-to-last element sits at some j < i with nums[j] < nums[i]; everything up to j is an increasing subsequence ending at j, so it has at most dp[j] elements and the whole has at most dp[j] + 1. The transition tries every such j, so dp[i] is never too small. It is never too large either, because the longest subsequence ending at the chosen j, followed by nums[i], is real. By induction from left to right every cell is right, and since every subsequence ends somewhere, the LIS is the largest cell.

The code

The function returns one longest strictly increasing subsequence, rebuilt from the parent links in the animation.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// One longest strictly increasing subsequence of nums, in O(n²).
vector<int> longestIncreasing(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return {};
    vector<int> dp(n, 1);       // dp[i] = longest increasing subsequence ending at i
    vector<int> parent(n, -1);  // the index before i in that subsequence
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {  // nums[i] extends the subsequence ending at j
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
    }
    int end = 0;  // the answer is the best cell, not the last one
    for (int i = 1; i < n; i++)
        if (dp[i] > dp[end]) end = i;
    vector<int> lis(dp[end]);
    for (int i = end, k = dp[end] - 1; i != -1; i = parent[i], k--) lis[k] = nums[i];  // walk back
    return lis;
}

string joined(const vector<int>& values) {
    string s;
    for (int v : values) s += (s.empty() ? "" : " ") + to_string(v);
    return s;
}

int main() {
    vector<vector<int>> examples = {{5, 2, 8, 6, 3, 6, 9, 7, 1}, {10, 9, 2, 5, 3, 7, 101, 18}};
    for (const vector<int>& nums : examples) {
        vector<int> lis = longestIncreasing(nums);
        cout << joined(nums) << ": length " << lis.size() << ", one LIS " << joined(lis) << "\n";
    }
    return 0;
}

public class Main {
    // One longest strictly increasing subsequence of nums, in O(n²).
    static int[] longestIncreasing(int[] nums) {
        int n = nums.length;
        if (n == 0) return new int[0];
        int[] dp = new int[n];      // dp[i] = longest increasing subsequence ending at i
        int[] parent = new int[n];  // the index before i in that subsequence
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            parent[i] = -1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {  // nums[i] extends the subsequence ending at j
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
        }
        int end = 0;  // the answer is the best cell, not the last one
        for (int i = 1; i < n; i++)
            if (dp[i] > dp[end]) end = i;
        int[] lis = new int[dp[end]];
        for (int i = end, k = dp[end] - 1; i != -1; i = parent[i], k--) lis[k] = nums[i];  // walk back
        return lis;
    }

    static String joined(int[] values) {
        StringBuilder s = new StringBuilder();
        for (int v : values) s.append(s.length() == 0 ? "" : " ").append(v);
        return s.toString();
    }

    public static void main(String[] args) {
        int[][] examples = {{5, 2, 8, 6, 3, 6, 9, 7, 1}, {10, 9, 2, 5, 3, 7, 101, 18}};
        for (int[] nums : examples) {
            int[] lis = longestIncreasing(nums);
            System.out.println(joined(nums) + ": length " + lis.length + ", one LIS " + joined(lis));
        }
    }
}

def longest_increasing(nums):
    """One longest strictly increasing subsequence of nums, in O(n²)."""
    n = len(nums)
    if n == 0:
        return []
    dp = [1] * n        # dp[i] = longest increasing subsequence ending at i
    parent = [-1] * n   # the index before i in that subsequence
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:  # nums[i] extends the subsequence ending at j
                dp[i] = dp[j] + 1
                parent[i] = j
    end = 0  # the answer is the best cell, not the last one
    for i in range(1, n):
        if dp[i] > dp[end]:
            end = i
    lis = [0] * dp[end]
    i, k = end, dp[end] - 1
    while i != -1:  # walk back
        lis[k] = nums[i]
        i, k = parent[i], k - 1
    return lis


def joined(values):
    return " ".join(map(str, values))


examples = [[5, 2, 8, 6, 3, 6, 9, 7, 1], [10, 9, 2, 5, 3, 7, 101, 18]]
for nums in examples:
    lis = longest_increasing(nums)
    print(f"{joined(nums)}: length {len(lis)}, one LIS {joined(lis)}")

// One longest strictly increasing subsequence of nums, in O(n²).
function longestIncreasing(nums) {
  const n = nums.length;
  if (n === 0) return [];
  const dp = new Array(n).fill(1); // dp[i] = longest increasing subsequence ending at i
  const parent = new Array(n).fill(-1); // the index before i in that subsequence
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
        // nums[i] extends the subsequence ending at j
        dp[i] = dp[j] + 1;
        parent[i] = j;
      }
    }
  }
  let end = 0; // the answer is the best cell, not the last one
  for (let i = 1; i < n; i++) if (dp[i] > dp[end]) end = i;
  const lis = new Array(dp[end]);
  for (let i = end, k = dp[end] - 1; i !== -1; i = parent[i], k--) lis[k] = nums[i]; // walk back
  return lis;
}

const joined = (values) => values.join(" ");

const examples = [
  [5, 2, 8, 6, 3, 6, 9, 7, 1],
  [10, 9, 2, 5, 3, 7, 101, 18],
];
for (const nums of examples) {
  const lis = longestIncreasing(nums);
  console.log(`${joined(nums)}: length ${lis.length}, one LIS ${joined(lis)}`);
}

5 2 8 6 3 6 9 7 1: length 4, one LIS 2 3 6 9
10 9 2 5 3 7 101 18: length 4, one LIS 2 5 7 101

Two nested loops make this O(n²): about three million comparisons for n = 2,500, but 5 × 10⁹ for n = 10⁵, which is far too slow.

The O(n log n) method: keep the smallest tails

The quadratic version scans every earlier element to find which subsequence to extend. The faster method keeps a summary that answers the same question with one binary search: tails[k] is the smallest value that ends any increasing subsequence of length k + 1 seen so far. Smaller is better, because a subsequence ending low is easier to extend. For each new value x, find the first tail not smaller than x: replace it with x, or append x if every tail is smaller. Dealing values onto piles like this is also called patience sorting.

1. tails[k] will hold the smallest value that ends any increasing subsequence of length k + 1. Each value goes to the first slot whose tail is not smaller than it; a new slot opens when every tail is smaller.
2. 5 is the first value: it opens slot 0, an increasing subsequence of length 1 ending in 5.
3. 2: the first tail not smaller than it is 5 in slot 0, found by binary search because tails is sorted. 2 takes its place: a length-1 subsequence can now end in 2.
4. 8 is larger than every tail [2], so it extends the longest subsequence: a new slot opens and the length becomes 2. Its arrow points at 2, the tail it extends.
5. 6: the first tail not smaller than it is 8 in slot 1. 6 takes its place, extending the length-1 subsequence that ends in 2: same length, smaller tail.
6. 3: the first tail not smaller than it is 6 in slot 1. 3 takes its place, extending the length-1 subsequence that ends in 2: same length, smaller tail.
7. 6 is larger than every tail [2, 3], so it extends the longest subsequence: a new slot opens and the length becomes 3. Its arrow points at 3, the tail it extends.
8. 9 is larger than every tail [2, 3, 6], so it extends the longest subsequence: a new slot opens and the length becomes 4. Its arrow points at 6, the tail it extends.
9. 7: the first tail not smaller than it is 9 in slot 3. 7 takes its place, extending the length-3 subsequence that ends in 6: same length, smaller tail.
10. 1: the first tail not smaller than it is 2 in slot 0. 1 takes its place: a length-1 subsequence can now end in 1. The 2 is buried, but 3 still points at it, so no subsequence is lost.
11. 4 slots, so the LIS has length 4. The tails [1, 3, 6, 7] are not an answer — the 1 comes last in the array — but the arrows are: from the last slot back, 7 → 6 → 3 → 2, so 2, 3, 6, 7.

Why tails stays sorted

Binary search needs tails sorted, and it always is, strictly. Behind every tail is a real subsequence of its length, and cutting the last value off the one behind tails[k + 1] leaves a subsequence of length k + 1 ending below tails[k + 1]:

1. Behind every tail is a real increasing subsequence of its length, found by following the parent arrows: [1], [2, 3], [2, 3, 6], [2, 3, 6, 7]. Each one ends in its slot's tail.
2. Drop the last value of the length-4 subsequence: [2, 3, 6] is increasing, has length 3 and ends in 6, below 7. tails[2] is the smallest such end, so tails[2] ≤ 6 < tails[3]. The same argument works for every slot, so tails is always strictly sorted.
3. Read in slot order, the tails [1, 3, 6, 7] come from different subsequences: the 1 sits at index 8, after the others, so the first step goes backwards. Their count is the LIS length; their values are not a subsequence.

The update is also exactly right. Slots before position k hold tails smaller than x, which x cannot improve; slots after it would need x to follow a tail at least as large as x. Position k is the one length x reaches with a better tail, so the number of slots is always the LIS length so far.

The code

To rebuild a real LIS, the tails store indices and every value remembers the tail to its left when it lands, the arrows in the animation. The search is written by hand so one function handles both comparisons explained next.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// One longest increasing subsequence in O(n log n): strictly increasing when
// strict is true, non-decreasing when it is false.
vector<int> longestIncreasing(const vector<int>& nums, bool strict) {
    vector<int> tails;                   // tails[k] = index of the smallest tail of length k + 1
    vector<int> parent(nums.size(), -1); // the index before i in the subsequence i ends
    for (int i = 0; i < (int)nums.size(); i++) {
        int lo = 0, hi = tails.size();   // binary search: first tail that x cannot follow
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            int t = nums[tails[mid]];
            if (strict ? t < nums[i] : t <= nums[i]) lo = mid + 1;
            else hi = mid;
        }
        if (lo > 0) parent[i] = tails[lo - 1];            // extend the subsequence one shorter
        if (lo == (int)tails.size()) tails.push_back(i);  // longer than every subsequence so far
        else tails[lo] = i;                               // same length, smaller tail
    }
    int k = tails.size();
    vector<int> lis(k);
    for (int i = k > 0 ? tails[k - 1] : -1; i != -1; i = parent[i]) lis[--k] = nums[i];
    return lis;
}

string joined(const vector<int>& values) {
    string s;
    for (int v : values) s += (s.empty() ? "" : " ") + to_string(v);
    return s;
}

void show(const vector<int>& nums, bool strict) {
    vector<int> lis = longestIncreasing(nums, strict);
    cout << joined(nums) << (strict ? " (strict)" : " (non-decreasing)") << ": length "
         << lis.size() << ", one LIS " << joined(lis) << "\n";
}

int main() {
    show({5, 2, 8, 6, 3, 6, 9, 7, 1}, true);
    show({10, 9, 2, 5, 3, 7, 101, 18}, true);
    show({1, 2, 2, 2, 3}, true);
    show({1, 2, 2, 2, 3}, false);
    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    // One longest increasing subsequence in O(n log n): strictly increasing when
    // strict is true, non-decreasing when it is false.
    static int[] longestIncreasing(int[] nums, boolean strict) {
        List<Integer> tails = new ArrayList<>();  // tails[k] = index of the smallest tail of length k + 1
        int[] parent = new int[nums.length];      // the index before i in the subsequence i ends
        for (int i = 0; i < nums.length; i++) {
            int lo = 0, hi = tails.size();        // binary search: first tail that x cannot follow
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                int t = nums[tails.get(mid)];
                if (strict ? t < nums[i] : t <= nums[i]) lo = mid + 1;
                else hi = mid;
            }
            parent[i] = lo > 0 ? tails.get(lo - 1) : -1;   // extend the subsequence one shorter
            if (lo == tails.size()) tails.add(i);          // longer than every subsequence so far
            else tails.set(lo, i);                         // same length, smaller tail
        }
        int k = tails.size();
        int[] lis = new int[k];
        for (int i = k > 0 ? tails.get(k - 1) : -1; i != -1; i = parent[i]) lis[--k] = nums[i];
        return lis;
    }

    static String joined(int[] values) {
        StringBuilder s = new StringBuilder();
        for (int v : values) s.append(s.length() == 0 ? "" : " ").append(v);
        return s.toString();
    }

    static void show(int[] nums, boolean strict) {
        int[] lis = longestIncreasing(nums, strict);
        System.out.println(joined(nums) + (strict ? " (strict)" : " (non-decreasing)") + ": length "
                + lis.length + ", one LIS " + joined(lis));
    }

    public static void main(String[] args) {
        show(new int[] {5, 2, 8, 6, 3, 6, 9, 7, 1}, true);
        show(new int[] {10, 9, 2, 5, 3, 7, 101, 18}, true);
        show(new int[] {1, 2, 2, 2, 3}, true);
        show(new int[] {1, 2, 2, 2, 3}, false);
    }
}

def longest_increasing(nums, strict):
    """One longest increasing subsequence in O(n log n): strictly increasing
    when strict is True, non-decreasing when it is False."""
    tails = []                  # tails[k] = index of the smallest tail of length k + 1
    parent = [-1] * len(nums)   # the index before i in the subsequence i ends
    for i, x in enumerate(nums):
        lo, hi = 0, len(tails)  # binary search: first tail that x cannot follow
        while lo < hi:
            mid = (lo + hi) // 2
            t = nums[tails[mid]]
            if (t < x) if strict else (t <= x):
                lo = mid + 1
            else:
                hi = mid
        if lo > 0:
            parent[i] = tails[lo - 1]   # extend the subsequence one shorter
        if lo == len(tails):
            tails.append(i)             # longer than every subsequence so far
        else:
            tails[lo] = i               # same length, smaller tail
    lis = []
    i = tails[-1] if tails else -1
    while i != -1:
        lis.append(nums[i])
        i = parent[i]
    return lis[::-1]


def joined(values):
    return " ".join(map(str, values))


def show(nums, strict):
    lis = longest_increasing(nums, strict)
    kind = "strict" if strict else "non-decreasing"
    print(f"{joined(nums)} ({kind}): length {len(lis)}, one LIS {joined(lis)}")


show([5, 2, 8, 6, 3, 6, 9, 7, 1], True)
show([10, 9, 2, 5, 3, 7, 101, 18], True)
show([1, 2, 2, 2, 3], True)
show([1, 2, 2, 2, 3], False)

// One longest increasing subsequence in O(n log n): strictly increasing when
// strict is true, non-decreasing when it is false.
function longestIncreasing(nums, strict) {
  const tails = []; // tails[k] = index of the smallest tail of length k + 1
  const parent = new Array(nums.length).fill(-1); // the index before i in the subsequence i ends
  for (let i = 0; i < nums.length; i++) {
    let lo = 0;
    let hi = tails.length; // binary search: first tail that x cannot follow
    while (lo < hi) {
      const mid = Math.floor((lo + hi) / 2);
      const t = nums[tails[mid]];
      if (strict ? t < nums[i] : t <= nums[i]) lo = mid + 1;
      else hi = mid;
    }
    if (lo > 0) parent[i] = tails[lo - 1]; // extend the subsequence one shorter
    if (lo === tails.length) tails.push(i); // longer than every subsequence so far
    else tails[lo] = i; // same length, smaller tail
  }
  let k = tails.length;
  const lis = new Array(k);
  for (let i = k > 0 ? tails[k - 1] : -1; i !== -1; i = parent[i]) lis[--k] = nums[i];
  return lis;
}

const joined = (values) => values.join(" ");

function show(nums, strict) {
  const lis = longestIncreasing(nums, strict);
  const kind = strict ? "strict" : "non-decreasing";
  console.log(`${joined(nums)} (${kind}): length ${lis.length}, one LIS ${joined(lis)}`);
}

show([5, 2, 8, 6, 3, 6, 9, 7, 1], true);
show([10, 9, 2, 5, 3, 7, 101, 18], true);
show([1, 2, 2, 2, 3], true);
show([1, 2, 2, 2, 3], false);

5 2 8 6 3 6 9 7 1 (strict): length 4, one LIS 2 3 6 7
10 9 2 5 3 7 101 18 (strict): length 4, one LIS 2 3 7 18
1 2 2 2 3 (strict): length 3, one LIS 1 2 3
1 2 2 2 3 (non-decreasing): length 5, one LIS 1 2 2 2 3

Strictly increasing or non-decreasing?

The two versions differ in one decision: what happens when x equals a tail.

1. Both versions deal the same values; they differ only in which tail the search stops at when x equals a tail. Strict stops at an equal tail and replaces it; non-decreasing goes past it.
2. x = 1 (index 0) is larger than every tail in both rows, so both append it: length 1.
3. x = 2 (index 1) is larger than every tail in both rows, so both append it: length 2.
4. The second 2. Strict: the first tail ≥ 2 is the 2 in slot 1, so it is replaced by an equal value and nothing grows. Non-decreasing: no tail is > 2, so it appends: length 3.
5. The third 2 does the same: strict replaces its 2 again and stays at length 2, while non-decreasing chains it on, length 4.
6. x = 3 (index 4) is larger than every tail in both rows, so both append it: lengths 3 and 5.
7. Strictly increasing gives 3 (1, 2, 3); non-decreasing gives 5, every value. In code that is lower_bound against upper_bound, bisect_left against bisect_right, or < against ≤ in the O(n²) table.

• Strictly increasing: search for the first tail greater than or equal to x: lower_bound in C++, bisect_left in Python.
• Non-decreasing: search for the first tail strictly greater than x: upper_bound in C++, bisect_right in Python.

In the O(n²) table the same switch is < against <=. Java's Arrays.binarySearch returns some matching index when values repeat, not the first, and JavaScript has no binary search, which is why the programs write the loop by hand.

Variations on the LIS

The most famous disguise is two dimensions that must both increase. In Russian Doll Envelopes, sort by width, then take a strict LIS of the heights; the tie-break for equal widths decides whether the answer is right.

1. An envelope fits inside another only if it is both narrower and shorter. Sort by width and take the LIS of the heights: with equal widths ordered by height ascending, the heights are [1, 2, 3, 4] and the LIS is 4.
2. But 2×2 and 2×3 have the same width, so neither fits inside the other. Ascending heights within one width let the LIS chain two of them: 4 is too many.
3. Sort equal widths by height descending instead: the heights become [1, 3, 2, 4]. Within one width they now fall, so a strictly increasing run takes at most one of them, and the LIS is 3.
4. The chain 1×1, 2×3 and 3×4 really nests, each narrower and shorter than the next. Sorting costs O(n log n) and the tails method another O(n log n).

• Counting the longest subsequences. Keep count[i] beside dp[i]: copy count[j] when dp[j] + 1 beats dp[i], add it on a tie. See Number of Longest Increasing Subsequence.
• Chains with a custom rule. Maximum Length of Pair Chain and Longest String Chain: sort so a follower always comes later, then run the O(n²) table with the rule in place of <.
• An order that is not total. In Delete Columns to Make Sorted III two columns can each fail to come before the other, so tails cannot be sorted; the O(n²) table still works.
• Fewest changes to make an array sorted. The elements kept form an increasing subsequence, so the answer is n minus the LIS, as in Minimum Operations to Make the Array K-Increasing (non-decreasing, k times).
• A triplet is enough. Increasing Triplet Subsequence needs only two tails: O(n) time, O(1) space.

The strict LIS also equals the longest common subsequence of the array and its sorted, de-duplicated copy.

Time and space complexity

At n = 10⁵ the tails method takes under two million steps. Prefer the O(n²) table when n is a few thousand at most, or when the problem needs counts or a comparison that is not a total order.

How to recognise an LIS problem

• The longest selection that keeps the original order, each element bigger than (or compatible with) the one before.
• Items with two dimensions that must both increase: sort by one, run an LIS on the other.
• The fewest deletions or changes that make a sequence sorted.
• The word subsequence with an ordering condition; "subarray" or "substring" usually means a scan or a sliding window instead.

Common mistakes

• Returning dp[n − 1]. The answer is the largest dp[i]; in the example dp[8] is 1.
• Printing tails as the answer. Only its length is right; its values are generally not a subsequence.
• Mixing up the two searches. upper_bound or bisect_right for a strict LIS lets equal values chain and overcounts.
• The wrong envelope tie-break. Equal widths sorted by ascending height let two of one width nest.
• Java's binarySearch as a lower bound. With repeated values it may return any match.

Practice in this order

1. Increasing Triplet Subsequence: two tails.
2. Longest Increasing Subsequence: write both versions.
3. Maximum Length of Pair Chain: sort, then a custom rule.
4. Longest String Chain: "can follow" means one letter added.
5. Number of Longest Increasing Subsequence: a count beside every dp value.
6. Russian Doll Envelopes: the sort and the fast method.
7. Delete Columns to Make Sorted III: an order that is not total.
8. Minimum Operations to Make the Array K-Increasing: n minus an LIS, k times.

The dynamic programming problem list has the rest. Next on the road: two-dimensional tables, starting with the 0/1 knapsack problem.