Longest Increasing Subsequence
Medium
Array
Binary Search
Dynamic Programming
Given an integer array `nums`, return *the length of the longest **strictly increasing*** *subsequence*.
Example 1
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Example 2
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3
Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints

  • •1 <= nums.length <= 2500
  • •-10⁴ <= nums[i] <= 10⁴
Time Complexity
O(n log n)
Space Complexity
O(n)
14
Case 1
Input: [10,9,2,5,3,7,101,18]
Expected: 4
Case 2
Input: [0,1,0,3,2,3]
Expected: 4
Case 3
Input: [7,7,7,7,7,7,7]
Expected: 1