Longest Increasing Subsequence Length
medium
Dynamic ProgrammingBinary SearchArrayDp 1dBinary Search On Answer
Asked atGoogleAmazonMicrosoftMeta
Problem Description
Given an integer array `sequence`, return the length of the **longest strictly increasing subsequence** (LIS).
A **subsequence** is derived by deleting some (or no) elements from the array without changing the relative order of the remaining elements.
**Example 1:**
```
Input: sequence = [4, 10, 4, 3, 8, 9]
Output: 3
Explanation: The LIS is [4, 8, 9] of length 3.
```
**Example 2:**
```
Input: sequence = [7, 2, 5, 1, 6, 4, 8]
Output: 4
Explanation: One LIS is [2, 5, 6, 8] of length 4.
```
Constraints
- 1 <= sequence.length <= 2500
- -10^4 <= sequence[i] <= 10^4
Follow-up
Can you also reconstruct the actual subsequence (not just its length) in O(n log n) time?
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.