Given an array of integers, find the length of the longest subsequence such that all elements of the subsequence are sorted in increasing order.

Think of a Traffic Jam:

1. You are looking at a line of cars.
2. You want to pick the most cars possible to move forward, but once a car moves, every car behind it must be taller (or faster/larger) than the one before.
3. If you pick a car of height 5, the next car you pick must be height > 5.
4. DP helps you look back and say: "If I choose this car, what's the longest chain I already built ending with a car smaller than this one?"

---

The DP State

dp[i] = Length of the longest increasing subsequence ending at index i.

• dp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i].

Complexity

• Time (Standard DP): $O(n^2)$.
• Time (Optimized): $O(n \log n)$ using Binary Search and a "tails" array.
• Space: $O(n)$.

---

javascript Standard
/**
 * LIS - O(n^2)
 */
function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;
  
  const dp = new Array(nums.length).fill(1);
  let maxLen = 1;

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    maxLen = Math.max(maxLen, dp[i]);
  }

  return maxLen;
}

---

Variations

• Maximum Sum Increasing Subsequence: Instead of dp[j] + 1, use dp[j] + nums[i].
• Russian Doll Envelopes: Sorting envelopes by width and finding LIS on heights.
• Longest String Chain: A variation where "increasing order" is defined by adding one character.

Follow-up

If the interviewer asks for $O(n \log n)$, tell them about the Patience Sorting algorithm. It maintains a list of the smallest possible tail for every increasing subsequence of a certain length. 📶