Longest Increasing Subsequence

Difficulty: Hard

Problem

Given an integer array, return the length of the longest STRICTLY increasing subsequence. Elements picked left to right (order kept, skips allowed) where each is larger than the one before. The classic that teaches DP's most subtle state definition.

Example

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: One longest increasing subsequence is [2, 3, 7, 101], length 4. ([2, 5, 7, 18] works too.)

Brute-force approach

Enumerating all 2ⁿ subsequences is hopeless. The guided walkthrough shows why and builds the O(n²) DP directly.

Optimal approach

Key insight: Pin the state to 'chains ENDING at i' and the impossible question 'what's the best subsequence?' becomes a checkable one: 'which smaller earlier ending can I extend?'

For each index i, dp[i] = 1 + the best dp[j] over earlier smaller values. The answer is the maximum over all endings.

Steps

  1. State: dp[i] = length of the longest increasing chain ending exactly at i
  2. Every dp[i] starts at 1 (the element alone)
  3. For each j < i with nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1)
  4. Answer: max over the whole dp array

Time complexity: O(n²) · Space complexity: O(n)