Compute length of longest increasing subsequence
Quick Overview
This question evaluates understanding of subsequences, dynamic programming and algorithmic optimization for array processing, and is categorized under Coding & Algorithms; it emphasizes practical application of algorithm design and complexity analysis rather than purely theoretical knowledge.
You are given an integer array nums of length n.
A subsequence of nums is a sequence that can be derived from nums by deleting zero or more elements without changing the order of the remaining elements. The elements of the subsequence do not need to be contiguous in the original array.
A subsequence is called strictly increasing if every element is strictly greater than the previous one.
Task: Return the length of the longest strictly increasing subsequence of nums.
Example 1
Input:
nums = [10, 9, 2, 5, 3, 7, 101, 18]
One longest strictly increasing subsequence is [2, 3, 7, 101], so the answer is 4.
Output:
4
Example 2
Input:
nums = [0, 1, 0, 3, 2, 3]
One longest strictly increasing subsequence is [0, 1, 2, 3], so the answer is 4.
Output:
4
Example 3
Input:
nums = [7, 7, 7, 7]
Every strictly increasing subsequence has length 1 (any single element), so the answer is 1.
Output:
1
Constraints
-
1 <= n <= 2 * 10^5 -
-10^9 <= nums[i] <= 10^9
Design an algorithm that can handle the largest constraint efficiently.