300. Longest Increasing Subsequence
1. Description
Given an integer array nums, return the length of the longest strictly increasing subsequence.
2. Example
Example 1
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: 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
3. Constraints
- 1 <= nums.length <= 2500
- $-10^4$ <= nums[i] <= $10^4$
4. Solutions
Dynamic Programming
n = nums.size()
Time complexity: O($n^2$)
Space complexity: O(n)
class Solution {
public:
int lengthOfLIS(const vector<int> &nums) {
const int n = nums.size();
vector<int> length_end_at(n, 1);
int max_length = 1;
for (int i = 1; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (nums[i] > nums[j]) {
length_end_at[i] = max(length_end_at[j] + 1, length_end_at[i]);
}
if (length_end_at[i] == i + 1) {
break;
}
}
max_length = max(length_end_at[i], max_length);
}
return max_length;
}
};
Dynamic Programming && Binary Search
n = nums.size()
Time complexity: O(nlogn)
Space complexity: O(n)
class Solution {
public:
int lengthOfLIS(const vector<int> &nums) {
const int n = nums.size();
vector<int> last_value_at_len(n + 1);
last_value_at_len[1] = nums[0];
int max_length = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > last_value_at_len[max_length]) {
++max_length;
last_value_at_len[max_length] = nums[i];
} else {
auto iter = lower_bound(
last_value_at_len.begin() + 1, last_value_at_len.begin() + max_length + 1, nums[i]);
*iter = nums[i];
}
}
return max_length;
}
};