Longest Increasing Subsequence

Longest Increasing Subsequence is a classic dynamic programming problem. Dynamic programming is a way to solve a big problem by breaking it into small pieces, solving each piece once, and saving the answer. This one tests two things at once. First, can you spot the small repeated subproblem. Second, can you push past the obvious solution to a faster one using binary search.

🎯 The Problem

You get an array of numbers and you return the length of the longest increasing subsequence.

• A subsequence is a list made by deleting some numbers but keeping the rest in order.
• The numbers do not need to be next to each other. You can skip around.
• Increasing means each number is strictly larger than the one before it.
• You return a length, not the actual numbers.

For [10, 9, 2, 5, 3, 7, 101, 18], one increasing subsequence is 2, 3, 7, 101. Its length is 4. No longer one exists. So the answer is 4.

Input:  nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4

Explanation: The longest increasing subsequence is [2, 3, 7, 101], with length 4.

This diagram shows one valid increasing path through the array. We skip the numbers that break the order.

🐢 Approach 1: Plain Recursion (Brute Force)

Try every subsequence by keeping or skipping each number.

The idea:

• At each number you choose to keep it or skip it.
• If you keep it, the next number you keep must be larger.
• A function from a position and a last-picked value returns the longest run from there.

How it works:

• One call skips the current number.
• One call takes it, but only if it is larger than the last picked value.
• Return the longer of the two.

Why it is weak:

• The same position with the same last value gets solved again and again.
• These repeats are overlapping subproblems, the same small question many times.
• The branching doubles, so it is about O(2ⁿ). Too slow.

Here is the plain recursion code:

def length_of_lis(nums):
    def dfs(index, prev_index):
        if index == len(nums):
            return 0
        skip = dfs(index + 1, prev_index)
        take = 0
        if prev_index == -1 or nums[index] > nums[prev_index]:
            take = 1 + dfs(index + 1, index)
        return max(take, skip)

    return dfs(0, -1)

⚡ Approach 2: Memoization (Better)

Save the answer for each state so it is solved only once.

The idea:

• Each state is the current position and the index of the last picked number.
• Store the longest run for each state.

How it works:

• The first time a state comes up, compute it and save it.
• Next time, read the saved value back.

Why it is fast:

• Each state runs once.
• Time drops to about O(n²).

Here is the memoized recursion:

from functools import lru_cache


def length_of_lis(nums):
    @lru_cache(None)
    def dfs(index, prev_index):
        if index == len(nums):
            return 0
        skip = dfs(index + 1, prev_index)
        take = 0
        if prev_index == -1 or nums[index] > nums[prev_index]:
            take = 1 + dfs(index + 1, index)
        return max(take, skip)

    return dfs(0, -1)

⚡ Approach 3: Bottom-Up Tabulation (Better)

Fill a table from the smallest cases toward the answer.

The idea:

• Make an array dp the same length as the input.
• dp[i] is the length of the longest increasing subsequence that ends at index i.

How it works:

• Every number alone is a run of length one, so start each dp[i] at 1.
• For each i, look back at every earlier j.
• If nums[j] < nums[i], you can extend that run, so dp[i] = max(dp[i], dp[j] + 1).

Why it is fine:

• Tabulation needs no recursion stack, only loops.
• Each number looks back at all earlier numbers, so time is O(n²).
• The answer is the biggest value in dp.

This diagram shows the dp table filling for [10, 9, 2, 5, 3, 7]. Each cell looks back at smaller earlier numbers.

🚀 Approach 4: Binary Search With Tails (Best)

Keep a tails list and place each number with a quick search.

The idea:

• tails[k] is the smallest possible last number of an increasing run of length k+1.
• Walk the array once and place each number into tails.

How it works:

• For each number, find where it fits in tails using binary search.
• If it is bigger than everything in tails, add it to the end, which grows the longest run.
• Otherwise replace the first tails value that is greater than or equal to it.
• That keeps the tails as small as possible for future numbers.

Why it is best:

• Binary search cuts the search range in half each time, so each step is O(log n).
• The whole thing is O(n log n).
• The length of tails at the end is the answer.

Steps to Solve

1. Start with an empty list called tails.
2. Walk the array one number at a time.
3. Use binary search to find the first spot in tails that is greater than or equal to the number.
4. If no such spot exists, the number is the biggest so far, so add it to the end of tails.
5. Otherwise replace the value at that spot with the number.
6. The length of tails at the end is the length of the longest increasing subsequence.

#include <stdio.h>

int lengthOfLIS(int nums[], int n) {
    int tails[1000];
    int size = 0;  // current length of tails
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = size;
        while (lo < hi) {                 // binary search for the spot
            int mid = (lo + hi) / 2;
            if (tails[mid] < nums[i]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        tails[lo] = nums[i];              // place or replace
        if (lo == size) {
            size++;                       // number extended the longest run
        }
    }
    return size;
}

int main(void) {
    int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = 8;
    printf("%d\n", lengthOfLIS(nums, n));
    return 0;
}

4

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

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        // first tails value >= x
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);   // x extends the longest run
        } else {
            *it = x;              // keep tails small
        }
    }
    return (int)tails.size();
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << lengthOfLIS(nums) << endl;
    return 0;
}

4

public class LIS {
    public static int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;  // current length of tails
        for (int x : nums) {
            int lo = 0, hi = size;
            while (lo < hi) {                 // binary search for the spot
                int mid = (lo + hi) / 2;
                if (tails[mid] < x) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            tails[lo] = x;                    // place or replace
            if (lo == size) {
                size++;                       // x extended the longest run
            }
        }
        return size;
    }

    public static void main(String[] args) {
        int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
        System.out.println(lengthOfLIS(nums));
    }
}

4

import bisect


def length_of_lis(nums):
    tails = []
    for x in nums:
        # first tails value >= x
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)      # x extends the longest run
        else:
            tails[pos] = x       # keep tails small
    return len(tails)


nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis(nums))

4

function lengthOfLIS(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0;
    let hi = tails.length;
    while (lo < hi) {
      // binary search for the spot
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }
    tails[lo] = x; // place or replace
  }
  return tails.length;
}

const nums = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(lengthOfLIS(nums));

4

Let us walk through the Python version line by line and see why each piece is there.

import bisect


def length_of_lis(nums):
    tails = []
    for x in nums:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

The line import bisect brings in Python’s binary search helper. It saves us writing the search by hand.

The line tails = [] starts our list empty. Remember tails[k] holds the smallest possible last number of an increasing run of length k+1. Keeping these tails small leaves more room for later numbers to extend a run.

The loop walks each number x. The line pos = bisect.bisect_left(tails, x) finds the leftmost spot where x would keep tails sorted. In plain words it finds the first value that is greater than or equal to x.

The check if pos == len(tails) asks if x is bigger than everything in tails. If so, x can extend our longest run, so we append it. Otherwise tails[pos] = x replaces the first value that was greater than or equal to x. This does not change the length right now. But it lowers a tail, which helps future numbers fit.

The final len(tails) is the answer. The list length equals the length of the longest increasing subsequence. Trace [10, 9, 2, 5, 3, 7, 101, 18]. The tails become [2, 3, 7, 18] by the end, so the length is 4.

⏱️ Time and Space Complexity

Plain recursion repeats work, so it is O(2ⁿ). Memoization and the tabulation with the inner loop are O(n²), because each number looks back at all earlier numbers. The binary search version replaces that backward scan with a quick search, so it runs in O(n log n).

🧩 Key Takeaways

• ✅ A subsequence keeps the original order but can skip numbers. Increasing means each number is strictly larger.
• ✅ The O(n²) idea is dp[i], the longest run ending at index i, looking back at all smaller earlier numbers.
• ✅ Plain recursion repeats overlapping subproblems, so it is O(2ⁿ). Saving answers brings it to O(n²).
• ✅ The binary search version keeps a tails list of the smallest tail per length and runs in O(n log n).
• ✅ The tails list length is the answer, but its contents are not a real subsequence.

🚀 What’s Next?

• Decode Ways
• Word Break