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
Explanation: [2,3,7,101]
Example 2
Input: nums = [0,1,0,3,2,3]
Output: 4
Explanation: [0,1,2,3]
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4O(n²) DP: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]. O(n log n) with patience sort.
// O(n log n) using patience sort + binary search
public int lengthOfLIS(int[] nums) {
List<Integer> tails = new ArrayList<>();
for (int num : nums) {
int pos = Collections.binarySearch(tails, num);
if (pos < 0) pos = -(pos + 1); // insertion point
if (pos == tails.size()) tails.add(num);
else tails.set(pos, num); // replace to maintain smallest possible tail
}
return tails.size();
}Time: O(n log n) · Space: O(n)