Longest Increasing Subsequence

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps order but may drop elements; it does not have to be contiguous.

Intuition

What does dp[i] depend on? The longest increasing subsequence ending at i is one more than the longest ending at some earlier j where nums[j] < nums[i]:

dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i])

That's quadratic. We scan every earlier position for each i.

The n log n trick is a reframe: we don't actually need dp per index — we only need the smallest possible tail of an increasing subsequence of each length. Keep a sorted array tails where tails[k] = the smallest value that any length-(k + 1) increasing subsequence can end in. For each new x:

• If x is larger than every tail, it extends the longest sequence by one — push it.
• Otherwise, it replaces the first tail >= x. The subsequence of that length now ends on a smaller value, which is strictly better for extending later.

Final length of tails is the LIS length. The replacement uses binary search, giving O(n log n).

Approach

impl Solution {
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n == 0 {
            return 0;
        }
        let mut dp = vec![1i32; n];
        let mut best = 1;
        for i in 1..n {
            for j in 0..i {
                if nums[j] < nums[i] {
                    dp[i]= dp[i].max(dp[j] + 1);
                }
            }
            best= best.max(dp[i]);
        }
        best
    }
}

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

impl Solution {
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        let mut tails: Vec<i32> = Vec::with_capacity(nums.len());
        for x in nums {
            // First index where tails[k] >= x.
            let k = tails.partition_point(|&t| t < x);
            if k= tails.len() {
                tails.push(x);
            } else {
                tails[k]= x;
            }
        }
        tails.len() as i32
    }
}

function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];
  for (const x of nums) {
    // First index where tails[k] >= x.
    let lo = 0;
    let hi = tails.length;
    while (lo < hi) {
      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;
}

Trace

Patience sort on nums = [10, 9, 2, 5, 3, 7, 101, 18]:

Final tails.len() = 4. ✓ Note the final tails content looks like a plausible LIS, but that's coincidence — if the replacements crossed each other earlier, the stored values would no longer form a real subsequence of the input.

Edge cases

• nums = [] — return 0. The partition_point approach handles this naturally (empty tails); the DP form needs the explicit check.
• Strictly increasing input — every element pushes; tails.len() equals nums.len().
• All equal — return 1. Because the comparison is < (strict), every x after the first replaces tails[0] without extending.
• Duplicates in a generally-increasing sequence — replace semantics keep the smallest tail at each length, so [1, 2, 2, 3] returns 3, not 4.

Takeaway

When a DP recurrence looks like "max over all earlier states matching a predicate," check if the state space has extra structure you can exploit. Here the structure is: for each length, only the smallest tail matters. That's what lets us replace a per-index DP with a single sorted array.

This patience-sort reframe is one of the oldest tricks in competitive programming and shows up whenever "maintain best-so-far per category" is enough to answer the outer question. The same shape reappears in #673 (count LIS with back-pointers), #354 Russian Doll Envelopes (2D LIS after sort), and in the offline-query optimizations that underpin monotonic structures like #1143 LCS.