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)