leetExpert
Practice

Longest Increasing Subsequence

Module 24 · Dynamic Programming

Problem

Given an integer array nums, return the length of the longest STRICTLY increasing subsequence (elements need not be contiguous, but must preserve their original relative order). (LeetCode 300.)

Examples

Example 1

Inputnums = [10,9,2,5,3,7,101,18]Output4

Explanation. 2, 3, 7, 18 — or 2, 3, 7, 101

Example 2

Inputnums = [0,1,0,3,2,3]Output4

Explanation. 0, 1, 2, 3

Constraints

1 ≤ nums.length ≤ 2500.

Attempt it first

Two distinct solutions worth building, in order: first the O(n²) DP (genuinely the more natural first attempt), and then — as a real optimization, not just a faster implementation of the same idea — an O(n log n) approach borrowed from binary search. Before opening anything, define dp[i] = the length of the longest increasing subsequence that ENDS AT index i specifically (not "using the first i elements" — this distinction matters), and work out the recurrence in terms of all j < i with nums[j] < nums[i].