Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements.
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.
Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: The longest increasing subsequence is [0, 1, 2, 3], which has length 4.
We maintain a dp array where dp[i] represents the length of the longest increasing subsequence ending at index i.
For each element, we look back at all previous elements and if a smaller element is found, we can extend that subsequence.
- Initialize every dp[i] = 1 (every element alone is a subsequence of length 1).
- For each index i, iterate over all indices j < i. If nums[j] < nums[i], update dp[i] = max(dp[i], dp[j] + 1).
- The answer is the maximum value in the dp array.
public class LongestIncreasingSubsequence {
// O(n^2) DP approach
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
java.util.Arrays.fill(dp, 1);
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;
}
// O(n log n) Patience sort approach using binary search
public int lengthOfLISOptimal(int[] nums) {
java.util.List<Integer> tails = new java.util.ArrayList<>();
for (int num : nums) {
int lo = 0, hi = tails.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails.get(mid) < num) lo = mid + 1;
else hi = mid;
}
if (lo == tails.size()) tails.add(num);
else tails.set(lo, num);
}
return tails.size();
}
}
Complexity Analysis:
Time complexity: O(n²) for DP approach; O(n log n) for patience sort approach.
Space complexity: O(n) for the dp / tails array.