Longest Increasing Subsequence

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from the array by deleting some or no elements without changing the order of the remaining elements. For example, [3, 6, 2, 7] is a subsequence of [0, 3, 1, 6, 2, 2, 7].

Examples

Example 1:

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], which has length 4.

Example 2:

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: The longest increasing subsequence is [0, 1, 2, 3], which has length 4.

Example 3:

Input: nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1
Explanation: All elements are equal, so the longest strictly increasing subsequence has length 1.

Constraints

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

Expected Complexity

• Time: O(n log n) using patience sorting / binary search, or O(n^2) using DP
• Space: O(n)