#5MediumDynamic Programming· Patience Sorting with Binary Search

Longest Increasing Subsequence

Given an integer array `nums`, return the length of its longest **strictly increasing subsequence**. A subsequence keeps the original relative order of the elements it uses but may skip any number of elements. For example, `[2, 5, 9]` is a subsequence of `[2, 8, 5, 1, 9]`; `[5, 2]` is not. Aim for an `O(n log n)` solution.

Input format

nums: array of integers

Output format

Integer: length of the longest strictly increasing subsequence

Examples

Input: nums = [3, 1, 8, 2, 5, 9, 4]

Output: 4

One longest choice is [1, 2, 5, 9].

Input: nums = [7, 7, 7, 7]

Output: 1

Equal values do not count as increasing, so the best is a single element.

Input: nums = [-3, 10, -1, 0, 4, 2, 3]

Output: 5

One longest choice is [-3, -1, 0, 2, 3].

Constraints

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

Study first

Dynamic Programming Patterns
Binary Search & Search Spaces

#dynamic-programming
#binary-search
#arrays