Start learning free

LESSON 542 OF 678 · DYNAMIC PROGRAMMING

Longest Increasing Subsequence

Practice O(n2)

You get an array of integers nums.

Return the length of its longest strictly increasing subsequence.

A subsequence takes some of the elements (or all of them) and keeps their order. For example, [4, 5, 9] is a subsequence of [4, 8, 1, 5, 2, 6, 9].

Strictly increasing means each element is bigger than the one before it. So the same value can't appear twice.

 

Example 1:

Input: nums = [4, 8, 1, 5, 2, 6, 9]
Output: 4
Explanation: [4, 5, 6, 9] and [1, 2, 6, 9] both have 4 elements.
No strictly increasing subsequence has 5.
You return only the length, 4.

Example 2:

Input: nums = [5, 5, 6, 6, 7]
Output: 3
Explanation: The longest is [5, 6, 7].
Only one 5 and one 6 can be used.
Equal values don't count as increasing.

Example 3:

Input: nums = [9, 4, -1]
Output: 1
Explanation: The values only go down.
So the longest is any single element.

 

Constraints:

  • nums holds 1 to 2,500 elements.
  • Each element is from -10,000 to 10,000.

Note:

Your algorithm should run in O(n2) time and use O(n) extra space, where n is the length of nums.

A faster O(n log n) method exists. For each length, keep the smallest value that can end an increasing subsequence that long. Place every element in that list with a binary search.



Trying every subsequence is far too slow: 2500 elements have 22500 subsequences. Solve smaller versions of the problem instead: let dp[i] be the length of the longest strictly increasing subsequence that ends with nums[i]. Every dp[i] is at least 1: the element alone is such a subsequence.

Fill dp from left to right. For every earlier index j < i with nums[j] < nums[i], the element nums[i] can be added to the end of the best subsequence that ends at j, which gives the length dp[j] + 1. So dp[i] is 1 plus the largest such dp[j], or just 1 when no earlier element is smaller.
The longest subsequence can end anywhere, so the answer is the largest dp[i], not necessarily the last one.

Every pair j < i is looked at once, and there are n · (n - 1) / 2 pairs: O(n2) time. The table takes O(n) space.
STEP 1 OF 9
    Ctrl + Enter to check