Problem Description
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
- Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 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
-104 <= nums[i] <= 104
Forewords:
This blog aims to describe various solutions that improve the performance over time. I started with a fail brute-force solution, that, despite its intuitive, is too complicated to finish because its attempt to make logic for all possible scenarios in for loops. Then I have another brute-force solution using recursive approaches. Recursive approaches are powerful in a way that if we could know all possible inputs, the recursive calls themselves will make up all possible scenarios; in other words, a decision tree is automatically created.
However, writing a decision tree with recursive is itself not a top-down approach nor any of other DP approach without better optimizations. The third solution is of bottom-up approach.
Finally, we have a greedy solution. Greedy solutions are basically "common sense" solution. The "common sense" however is resulted from good experience, and understanding of common problem patterns.
Credits: all credits go to longvatrong111 who made all of those solutions.
Solution 1: Fail brute force approach.
Algorithm:
- we use for loop to traverse the input
numsarray and apply logics to choose elements ofnumsarray and put in the increasing subsequence. - the outermost for loop is to traverse through the
numsarray. - For each item in
numsarray:
- if current element is larger than the largest value in subsequence so far or larger than the previous item on the right, put it on the subsequence, increment the length of the subsequence.
if (nums[i]>largestInSubsequence && nums[i]<nums[right]){
length++;
largestInSubsequence = nums[i];
cout<<"basic case, i="<<i<<" ";
cout<<" add "<<nums[i]<<" length "<<length<<endl;
}- corner case: Note that a corner case may arise just because of our redundant logic, but would not be a corner case otherwise. In our case, because of how the limit of for loop is created, we have a corner case with multiple conditions
if (nums[i]== nums[right] && i==right && nums[left] < nums[right]){
length++;
}- a more "proper" corner case: No matter what solution you may use, you still have to address the same dilema, that is how pick the item for longest subsequence. A corner case maybe that the item is smaller than both imediate previous item and the largest value in the subsequence so far. For example, we have
nums= [1,2,15,4,5,6,100,200].nums[3]=4 < nums[3]=15, but a sequence[1,2,4,5,6,100,200]including nums[3] is a longer subsequence. Another example isnums=[1,3,6,7,9,4,10,5,6]. We see that a subsequence[1,3,6,7,9,10]is longer than[1,2,4,5,6]. Pickingnums[5]=4is not good at all. Therefore, if we take linear approach and attempt to satisfy all logic rules the come up with the subsequence in one go, it is impossible. We soon see that no amount ofif clauseis possible to address this situation. This will give rise to using recursive call to make up brute force solution.
Code:
class Solution { // 256 ms, faster than 42.84%
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
int result=1;
vector<int> dp(n, 1);
// right of subsequence
for (int right = 0; right < n; right++){
// left of subsequence
for (int left = 0; left <= right; left++){
int length=0;
int largestInSubsequence = -pow(10,4)-1;
// start adding increasing number on the left to subsequence:
for (int i = left; i <=right; i++){
// basic case: subsequence 1, 2, 3 ..
if (nums[i]>largestInSubsequence && nums[i]<nums[right]){
length++;
largestInSubsequence = nums[i];
}
// border case 1, 2, 3, 4 when nums[right]=4 and i=4
if (nums[i]== nums[right] && i==right && nums[left] < nums[right]){
length++;
}
// special case: 1, 2, 15, 4, 5, 6, 100, 200
// no logic statement is possible!!!!
}
result = max(result, length);
}
}
return result;
}
};Solution 2: Brute Force approach using Recursive Calls
- Recursive method is a good way to populate all possible scenarios. For each position in the array, we have 2 options: (1) add the element into current subsequences and (2) ignore. For (1) the element must be strictly larger than the last element of current subsequence. So for each position, tree decision splits into 2 branches. We can caculate easily with rescursive implemetation.
- Recursive call takes in the following parameters:
- index of the next position. When the recursive function is invoked, the next position becomes the current position, at which a subsequence may be formed by including the value at that position.
- Value from the last position or the value at the current position.
- The answer is returned by comparing the length of all subsequences when an item is included or not.
if (val < nums[idx]) {
ans = std::max(solve(nums, idx + 1, val), 1 + solve(nums, idx + 1, nums[idx])); }
/* else, can not add the current element into subsequence */
else {
ans = solve(nums, idx + 1, val);
}Code:
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int solve(vector<int>& nums, int idx, int val) {
/* Base case */
if (idx == nums.size()) return 0;
int ans = 0;
/* if the last value < current value, both (1) and (2) are possible */
if (val < nums[idx]) {
ans = std::max(solve(nums, idx + 1, val), 1 + solve(nums, idx + 1, nums[idx]));
}
/* else, can not add the current element into subsequence */
else {
ans = solve(nums, idx + 1, val);
}
return ans;
}
int lengthOfLISBruteForce(vector<int>& nums) {
/* the 2nd param is the starting index, the 3rd param is the value of the last element in the current subsequence */
return solve(nums, 0, INT_MIN);
}
int main() {
vector<int> test = {10, 9, 2, 5, 3, 7, 101, 18};
cout << lengthOfLISBruteForce(test) << endl;
return 0;
}Complexity Analysis:
- Time Complexity: O(N^N) because of recursive calls.
Solution 3: Bottom Up approach
- DP solution attemps to devide each problem into subproblems where the solution of earlier problems effect those of later subproblems.
- Each subproblem returns data, which is store in state. A DP array stores answers for subproblems in its elements. DP state variable identify the states. The recurrent relation between subproblems are expressed by DP equation. Thus for each DP approach, the following steps are used:
- step 1: choose DP state and its initial state. For this problem, the states are the length of the subsequences.
- step 2: choose DP state variable. For this problem, we use index of input array
numsas the state variable. - step 3: devise DP equation and logic. Two for loops are used. The outter for loop is used to pick up a item
Ifrom the input arraynums. The inner for loop is used to pick up all preceding items before the item from the outer for loop. It is then decided if the preceding items could be included into the subsequence starting from 0 to the itemI
for(int i = 0; i < nums.size(); ++i) { // pick up item I int maxLen = 0;
for(int j = 0; j < i; ++j) { // pick up preceding items
if (nums[j] < nums[i])
maxLen = max(maxLen, dp[j]); // if item could be included in the subsequence from 0 to I, then make compare with current length }
dp[i] = maxLen + 1; // current length of the subsequence increments by 1 ans = max(ans, dp[i]);
}
return ans;- or similar logic:
for (int right = 0; right < n; right++)
for (int left = 0; left < right; left++)
if (nums[right] > nums[left] && dp[right] < dp[left] + 1)
dp[right] = dp[left] + 1;Code:
#include<vector>
#include<iostream>
using namespace std;
/*
dp solution
Observe:
- The answer for subarray of size i is dp[i]
dp[i] = the max answer of all dp[j] that j < i and nums[j] < nums[i]
*/
int lengthOfLISDP(vector<int>& nums) {
vector<int> dp (nums.size(), -1);
int n = nums.size();
int ans = 0;
for(int i = 0; i < nums.size(); ++i) {
int maxLen = 0;
for(int j = 0; j < i; ++j) {
if (nums[j] < nums[i])
maxLen = max(maxLen, dp[j]);
}
dp[i] = maxLen + 1;
ans = max(ans, dp[i]);
}
return ans;
}
int main() {
vector<int> test = {10, 9, 2, 5, 3, 7, 101, 18};
cout << lengthOfLISDP(test) << endl;
return 0;
}Complexity Analysis:
- Time complexity: O(N^2) because of two nested for loops resulting in 1 + 2 + 3 + 4 + ... + N = 2Nβ(N+1)β operations, or time complexity of O(N^2).
- Space complexity: O(N) The only extra space we use relative to input size is the
dparray, which is the same length asnums.
Solution 4: Greedy Approach -
This method provides a way to keep a best sequence while we iterative over the array
- Starting case: The best sequence when i = 0 is nums[0]
- If we have a current best sequence and we meet a new val:
(1) if val > all elements, can easily add it into the tail
(2) if not, can replace lower_bound of val in the sequence by val because:
+ it doesn't change the current result and all next results (e.g 2 9 10 14 and 2 4 10 14 have the same length no matter what the next numbers are)
+ it is always better way to find an optimal sequence, because we reduce the condition for (1) as much as possible.
Leetcode user xungao explains:
"Think of the sub array as a mapping from sequence length to the smallest ending value of that length. For instance, if there are totally two 3-element sequences [1, 2, 3] and [1, 2, 10], we say 3 is the smallest ending value of all 3-element sequences. If any sub-sequent value has a chance to extend a 3-element sequence into a 4-element sequence, it has to be greater than 3.
We use the i-th (1-based) element of the sub array to remember the smallest ending value of all i-element sequences. Note that the values in this array will be ever increasing since a longer sequence will need a larger ending value.
When we add a new value, we check to see if it can extend a sequence of a certain length.
We can try longer sequences first. For instance, if currently the sub array has 5 values, we first check if the new value can extend a 5-element sequence, so we compare it with the 5th value in sub, which remembers the smallest ending value of all 5-element sequences. Case 1: If the new value is bigger, it can extend and now we have a 6 element sequence with this new value as ending value. So we add the new value as the 6th value in sub, meaning that the new value is the smallest ending value of all 6-element sequences.
Case 2: If the new value is less than or equal to the 5th value in sub, we say OK we cannot extend any 5-element sequence, so we try extending 4-element sequence. So we compare it with the 4th value in sub. we repeat the process going from longer sequences to shorter sequences until we find a length that we can extend. For example, after we go through the 5-th, 4th and 3rd values in sub, the 2nd value is the first that's less than the new value, we know that the new value can extend a 2-element sequence and the new value will be a smaller ending value (than the current 3rd value) for all 3-element sequences, so we update the 3rd value of sub to the new value."
In order word, this method doesn't return the longest increasing subsequence but only find the length of longest increasing subsequence by finding the ending values of sequences of 2 , 3, 4, and so on.
Complexity Analysis:
Given NN as the length of nums,
- Time complexity: O(N log(N)). Linear for loop has complexity O(N). The lower_bound function uses Binary Search, which uses Nlog(N) time.
- Space complexity: O(N). When the input is strictly increasing, the
subarraybestArrwill be the same size as the input.
#include<vector>
#include<iostream>
using namespace std;
int lengthOfLISGreedy(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> bestArr;
bestArr.push_back(nums[0]);
for (int i = 1; i < n; ++i) {
auto it = lower_bound(bestArr.begin(), bestArr.end(), nums[i]);
// Case 1: nums[i] > the last value
if (it == bestArr.end())
bestArr.push_back(nums[i]);
// Case 2:
else *it = nums[i];
}
return bestArr.size();
}
int main() {
vector<int> test = {10, 9, 2, 5, 3, 7, 101, 18};
cout << lengthOfLISGreedy(test) << endl;
return 0;
}