Longest Rising Subsequence

Medium1-D Dynamic Programming

Problem

Given an integer array nums, pick some of its elements (keeping their original order, not necessarily adjacent) so that each picked value is strictly greater than the previous picked value.

Return the largest number of elements you can pick.

Example 1

Input:
nums = [6, 2, 7, 3, 4, 9, 1]
Output:
4

2, 3, 4, 9 is rising and has 4 elements; no rising pick has 5.

Example 2

Input:
nums = [4, 4, 4, 4]
Output:
1

Equal values do not rise.

Constraints

  • 1 ≤ nums.length ≤ 2500
  • -10^4 ≤ nums[i] ≤ 10^4
  • An O(n²) solution is expected here; an O(n log n) one is a welcome follow-up.

Hint

Show the first hint

Fix the LAST element of the rising pick. What does the best pick ending at index i look like?

Walkthrough

How to approach it

01Clarify before coding

  • Strictly increasing? Yes: equal values cannot both be picked.
  • Do I return the length or the subsequence? Only the length.
  • Must the elements be adjacent? No: that would be the much easier contiguous-run problem.

02Brute force

Try every subset of indices, keep those that are strictly increasing, and take the largest.

Cost: O(2^n · n): infeasible past n ≈ 25.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.