https://leetcode-cn.com/problems/longest-increasing-subsequence/submissions/
最简单的O(n^2)思路。
首先，用一个vector记录每一个数字为结尾的最大递增子序列的的长度的最大值。然后就是一个双层循环，先在外层中遍历数组中的每一个数字，再在内层中遍历该元素之前的每一个元素寻找以它为结尾的最大递增子序列的长度的最大值。
在内层循环中，可以有一个剪枝的方法，就是j不必须遍历到0，而只需要遍历到它前面数字的数目比now_max_len小即可（j>=now_max_len-1）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int l = nums.size();
if(l==0) return 0;
vector<int> records(l, 1);
int max_len = 1;
for(int i=1; i<l; ++i) {
int now_max_len = 1;
for(int j=i; j>=now_max_len-1; --j) {
if(nums[j]<nums[i] && records[j]+1>now_max_len) {
now_max_len = records[j]+1;
}
}
records[i] = now_max_len;
max_len = now_max_len>max_len ? now_max_len : max_len;
}
return max_len;
}
};
|
将上面使用vector顺序查找比nums[i]小的元素替换为使用map（红黑树）查找，速率反而降低了很多，说明红黑树O(klogn)的代价要比O(n)的代价高，其中k为nums中nums[i]左边比当前元素nums[i]小的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int l = nums.size();
if(l==0) return 0;
map<int, int> records;
int max_len = 1;
for(int i=0; i<l; ++i) {
int now_max_len = 1;
int ni = nums[i];
records.insert(make_pair(ni, 1));
for(auto j=records.begin(); j!=records.lower_bound(ni); ++j) {
if(j->second+1>now_max_len) {
now_max_len = j->second+1;
}
}
records[ni] = now_max_len;
max_len = now_max_len>max_len ? now_max_len : max_len;
}
return max_len;
}
};
|
还可以用贪心+二分法继续优化算法。关键思路是使用records数组去记录一个最长上升的序列，该序列虽然可能不是最终的结果，但它的长度是对的。
得到该数组的具体方法是：遍历nums数组中的每一个数字n，如果n大于records数组中最大的数字，则将n添加到records数组最右侧，否则，用n替换刚好大于它的那个数字，在查找该数字的时候，使用二分法进行查找。
这样，算法的整体时间复杂度降为O(n*logn)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int binSearch(vector<int>& records, int target) {
int i = 0, j = records.size()-1;
while(i<=j) {
int m = (i+j)/2;
if(target == records[m]) return m;
if(target > records[m]) i = m+1;
else j = m-1;
}
return i;
}
int lengthOfLIS(vector<int>& nums) {
int l = nums.size();
if(l<2) return l;
vector<int> records;
for(int n:nums) {
int i = binSearch(records, n);
if(i>=records.size()) records.push_back(n);
else records[i] = n;
}
return records.size();
}
};
|
此外，还有一种比较有意思的方法，是将求最长递增子序列长度的问题转换为求最长公共子序列的问题。
其做法十分简单，是将nums数组拷贝一份并排序，形成一个递增的序列，然后求nums数组和该递增序列的公共子序列。需要注意排序后的序列并不是严格递增的（可能会有重复的元素），所以需要进行一些逻辑判断来去重。
当然，这种方法的时间复杂度同样为O(n^2)，而且还要进行数组的排序，和上一种比效率还是低了不少，而且还需要一个二维数组进行dp，空间上也会多很多，所以并不是一个很合算的方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int l = nums.size();
if(l<=1) return l;
vector<int> targets(nums);
sort(targets.begin(), targets.end());
vector<vector<int>> dp(l, vector<int>(l, 0));
for(int i=0; i<l; ++i) {
for(int j=0; j<l; ++j) {
if(nums[i]==targets[j]) {
if(i>0 && j>0){
if(targets[j-1]==targets[j]) dp[i][j] = dp[i][j-1];
else dp[i][j] = dp[i-1][j-1]+1;
}
else dp[i][j] = 1;
} else {
if(i>0 && j>0) dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
else if(i>0) dp[i][j] = dp[i-1][j];
else if(j>0)dp[i][j] = dp[i][j-1];
}
}
}
return dp[l-1][l-1];
}
};
|