Longest Increasing Subsequence

medium

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

Test Cases

Copy an input into the main harness and Run to verify

Input

nums = [10,9,2,5,3,7,101,18]

Expected Output

4

Explanation: The subsequence [2,3,7,101] has length 4.

Input

nums = [0,1,0,3,2,3]

Expected Output

4

Input

nums = [7,7,7,7,7,7,7]

Expected Output

1

Hint 1 — click to reveal

O(n^2): dp[i] = 1 + max(dp[j]) over j < i with nums[j] < nums[i].

Hint 2 — click to reveal

O(n log n): maintain 'tails' — the smallest possible tail for each subsequence length.

Java Compiler