Problem
You are given an integer arraynums. Return the length of the longest strictly increasing subsequence.
A subsequence is created by deleting some elements without changing the order of the remaining elements. The elements do not need to be adjacent.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [10,9,2,5,3,7,101,18]Output
4Explanation
One possible longest increasing subsequence is:[2,3,7,101]Solution
This problem can be solved using Memoization.At every index, we have two choices: skip the current element or include it in the subsequence.
We can include the current element only if it is greater than the previously selected element. Therefore, the result depends on two values: the current index and the previous index.
If we skip the current element, we move to the next index while keeping the same previous element. If the current element is greater than the previous element, we can include it and make it the new previous element.
We return the maximum of these two choices.
The same combination of
currentIndex and previousIndex can occur multiple times, so we store the result in a memoization table.
Since
previousIndex can be -1 when no element has been selected yet, we use previousIndex + 1 as the column index in the memoization array.
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
Integer[][] memo = new Integer[n][n + 1];
return longest(nums, 0, -1, memo);
}
private int longest(int[] nums, int currentIndex, int previousIndex, Integer[][] memo) {
// Reached the end of the array
if (currentIndex == nums.length)
return 0;
// Return the cached result
if (memo[currentIndex][previousIndex + 1] != null)
return memo[currentIndex][previousIndex + 1];
// Skip the current element
int skip = longest(nums, currentIndex + 1, previousIndex, memo);
int include = 0;
// Include if it keeps the sequence increasing
if (previousIndex == -1 || nums[previousIndex] < nums[currentIndex])
include = 1 + longest(nums, currentIndex + 1, currentIndex, memo);
// Store and return the maximum of both choices
return memo[currentIndex][previousIndex + 1] = Math.max(skip, include);
}
}Complexity
There areO(nĀ²) possible combinations of currentIndex and previousIndex, and each state is calculated only once.
Therefore, the time complexity is
O(nĀ²). The memoization table requires O(nĀ²) space, while the recursion stack can grow up to O(n).
Tabulation Approach
In the bottom-up approach, letdp[i] represent the length of the longest increasing subsequence ending at index i.
Every element by itself forms an increasing subsequence of length
1.
dp[i] = 1j, if nums[j] < nums[i], we can extend the increasing subsequence ending at j.
dp[i] = max(dp[i], dp[j] + 1)
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int longest = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// Extend an increasing subsequence.
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
longest = Math.max(longest, dp[i]);
}
return longest;
}
}
Complexity
For every element, we compare it with all previous elements, resulting inO(nĀ²) time complexity.
The DP array requires
O(n) space.
Optimized Approach
The problem can be further optimized using Binary Search, reducing the time complexity toO(n log n).
We maintain a
tails array where tails[i] represents the smallest possible ending value of an increasing subsequence of length i + 1.
For each number, we use binary search to find its position in the
tails array. If the number is larger than all existing values, it extends the longest subsequence. Otherwise, it replaces an existing value with a smaller ending value, which gives more opportunities to extend the subsequence later.
class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int num : nums) {
int left = 0;
int right = size;
// Find the first value greater than or equal to num.
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = num;
if (left == size) {
size++;
}
}
return size;
}
}
Complexity
Each element is processed once, and binary search takesO(log n) for each element. Therefore, the total time complexity is O(n log n).
The
tails array requires O(n) space.