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^4The direct O(n^2) DP: dp[i] = length of the longest increasing subsequence ENDING at index i, built by checking every earlier index j.
dp[i] = 1 + max(dp[j]) for every j < i where nums[j] < nums[i] — or just 1 if no such j exists.
The O(n log n) improvement replaces the O(n) inner scan with binary search, by maintaining a different kind of state: not 'best ending here,' but 'smallest possible tail for each achievable length.'
public int lengthOfLISDP(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1); // every element is a subsequence of length 1 on its own
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}Time: O(n^2) · Space: O(n)