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

The Longest Increasing Subsequence (LIS) is the length of the longest subsequence whose elements are in strictly increasing order. For [10, 9, 2, 5, 3, 7, 101, 18], an LIS is [2, 3, 7, 18] (length 4). This page gives the intuitive O(n²) DP first, then the faster O(n log n) approach using binary search.

The O(n²) dynamic programming

Think of each index as a possible ending of an increasing subsequence.

State: dp[i] = length of the longest increasing subsequence that ends at index i.
Transition: dp[i] = 1 + max(dp[j]) over all j < i with a[j] < a[i]; if none qualifies, dp[i] = 1.
Base case: every element alone is a subsequence of length 1, so dp[i] starts at 1.

The answer is the maximum over all dp[i] (the LIS need not end at the last element).

int lengthOfLIS(const std::vector<int>& a) {
    int n = a.size();
    if (n == 0) return 0;
    std::vector<int> dp(n, 1);
    int best = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (a[j] < a[i])
                dp[i] = std::max(dp[i], dp[j] + 1);
        best = std::max(best, dp[i]);
    }
    return best;
}

int lengthOfLIS(int[] a) {
    int n = a.length;
    if (n == 0) return 0;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int best = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (a[j] < a[i])
                dp[i] = Math.max(dp[i], dp[j] + 1);
        best = Math.max(best, dp[i]);
    }
    return best;
}

function lengthOfLIS(a) {
  const n = a.length;
  if (n === 0) return 0;
  const dp = new Array(n).fill(1);
  let best = 1;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++)
      if (a[j] < a[i])
        dp[i] = Math.max(dp[i], dp[j] + 1);
    best = Math.max(best, dp[i]);
  }
  return best;
}

def length_of_lis(a):
    n = len(a)
    if n == 0:
        return 0
    dp = [1] * n
    best = 1
    for i in range(n):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
        best = max(best, dp[i])
    return best

That’s O(n²) time, O(n) space — fine up to a few thousand elements.

The O(n log n) approach

Maintain an array tails, where tails[k] is the smallest possible tail value of any increasing subsequence of length k+1. Scan the input; for each value x, binary-search the first tails entry >= x and overwrite it (or append if x is larger than all). The length of tails is the LIS length. tails is not the LIS itself, but its size is always correct.

int lengthOfLIS(const std::vector<int>& a) {
    std::vector<int> tails;
    for (int x : a) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

int lengthOfLIS(int[] a) {
    List<Integer> tails = new ArrayList<>();
    for (int x : a) {
        int lo = 0, hi = tails.size();
        while (lo < hi) {                       // first index with tails[idx] >= x
            int mid = (lo + hi) >>> 1;
            if (tails.get(mid) < x) lo = mid + 1;
            else hi = mid;
        }
        if (lo == tails.size()) tails.add(x);
        else tails.set(lo, x);
    }
    return tails.size();
}

function lengthOfLIS(a) {
  const tails = [];
  for (const x of a) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {                           // first index with tails[idx] >= x
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    if (lo === tails.length) tails.push(x);
    else tails[lo] = x;
  }
  return tails.length;
}

import bisect

def length_of_lis(a):
    tails = []
    for x in a:
        idx = bisect.bisect_left(tails, x)      # first index with tails[idx] >= x
        if idx == len(tails):
            tails.append(x)
        else:
            tails[idx] = x
    return len(tails)

Going deeper: This is “patience sorting.” Using lower_bound/bisect_left gives a strictly increasing LIS; switch to upper_bound/bisect_right to allow equal elements (longest non-decreasing subsequence). That one-line change is a classic interview follow-up.

Complexity comparison

Approach	Time	Space	Recovers the subsequence?
DP (`dp[i]`)	O(n²)	O(n)	yes (track predecessors)
Patience + binary search	O(n log n)	O(n)	yes (with extra bookkeeping)

Pitfall: The tails array is not a valid increasing subsequence — only its length is meaningful. If you need the actual elements, store a parent pointer per index (O(n²) DP) or record positions during the binary-search pass.

For beginners: Start by getting the O(n²) DP rock-solid; it’s the version you can reconstruct from memory. Reach for the O(n log n) variant only when n is large enough to need it.

Next, see counting and min-cost DPs in coin change, or revisit the recurrence styles in memoization vs tabulation.