1-D Dynamic Programming Increasing subsequences
527. Longest Increasing Subsequence
You are given an array of integers nums. Return the length of its longest strictly increasing
subsequence.
A subsequence keeps some of the elements, in their original order, and drops the rest. The kept elements do not have to be next to each other. It is strictly increasing when every kept element is bigger than the one kept before it, so two equal values can never both be in it.
Example 1
Input: nums = [5, 2, 8, 6, 3, 6, 9, 7]
4Explanation: One longest increasing subsequence is 2, 3, 6, 9, from indexes 1, 4, 5 and 6. Starting with 5, 8 looks good, but only the 9 is bigger than 8 after it.
Example 2
Input: nums = [7, 7, 7, 7]
1Explanation: All the values are equal, so a strictly increasing subsequence can keep only one of them.
Example 3
Input: nums = [-2, -9, 0, -4, 1000000000]
3Explanation: Both -2, 0, 1000000000 and -9, -4, 1000000000 have length 3.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.