这道题一直没能记住O(nlogL)的解法。
很详细的文，带路径输出：
http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html
相似题目：
https://leetcode.com/problems/increasing-triplet-subsequence/
https://leetcode.com/problems/russian-doll-envelopes/
300.longest-increasing-subsequence
https://leetcode.com/problems/longest-increasing-subsequence/
1.普通dp O(n^2)
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n,0);
int res = 0;
for(int i = 0; i < n; i++) {
int cur = 0;
for(int j = 0; j < i; j++) {
if(nums[j] < nums[i] && dp[j] > cur) {
cur = dp[j];
}
}
dp[i] = cur + 1;
if(dp[i] > res) res = dp[i];
}
return res;
}
};
2.Greedy+binary search优化
Robinson-Schensted-Knuth Algorithm
分三种情况，smallest，largest，mid。
class Solution {
int binarySearch(vector<int> &ends, int last, int x) {
int l = 0;
int r = last;
while(l < r) {
int m = l + (r - l)/2 + 1;
if(ends[m] >= x) {
r = m - 1;
} else {
l = m;
}
}
return l;
}
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n == 0) {return 0;}
vector<int> ends(n,0);
int last= 0;
ends[0] = nums[0];
for(int i = 1; i < n; i++) {
if(nums[i] < ends[0]) { //smallest
ends[0] = nums[i];
} else if(nums[i] > ends[last]) { //largest
ends[++last] = nums[i];
} else { //mid
int j = binarySearch(ends,last,nums[i]); //找到最大的小于x的值
ends[j+1] = nums[i];
}
}
return last+ 1;
}
};
Follow Up:
1.输出sequence
以下方法输出最后一个匹配上的sequence，如果想输出最先匹配上的，可以从后往前做longest decrease sequence，再输出。
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n == 0) {return 0;}
vector<int> ends(n,0);
vector<int> pos(n,0);
int last= 0;
ends[0] = nums[0];
pos[0] = 0;
for(int i = 1; i < n; i++) {
if(nums[i] < ends[0]) { //smallest
ends[0] = nums[i];
pos[i] = 0;
} else if(nums[i] > ends[last]) { //largest
ends[++last] = nums[i];
pos[i] = last;
} else { //mid
int j = binarySearch(ends,last,nums[i]); //找到最大的小于x的值
ends[j+1] = nums[i];
pos[i] = j+1;
}
}
//倒序输出
int k = n-1;
int i = last;
while(k >= 0) {
if(i == -1) break;
if(pos[k] == i) {
cout<<nums[k]<<" ";
i--;
}
k--;
}
return last+ 1;
}
2.求longest非严格递增的序列
binarySearch的时候找的时候，找<=x的值而不是<x的值即可。
3.输出所有的递增序列
感觉像是个排列组合问题。
334.increasing-triplet-subsequence
https://leetcode.com/problems/increasing-triplet-subsequence/
思路类似300，ends容量为3。
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n = nums.size();
if(n < 3) return false;
vector<int> ends(3);
int last = 0; //last = len - 1
ends[0] = nums[0];
for(int i = 1; i < n; i++) {
if(nums[i] < ends[0]) {
ends[0] = nums[i];
} else if(nums[i] > ends[last]) {
ends[++last] = nums[i];
if(last== 2) return true;
} else {
for(int j = 0; j < 3; j++) {
if(ends[j] == nums[i]) {
break;
} else {
if(nums[i] < ends[j])
ends[j] = nums[i];
}
}
}
}
return false;
}
};
354.Russian Doll Envelopes
https://leetcode.com/problems/russian-doll-envelopes/
暴力的思路就是用DP直接求解。
用binary search优化则用以下思路：
先用w排序，再对h用300做LIS即可，注意，因为要求严格递增，所以宽度需要有额外的判断。
见discuss，机智点在于排序的时候first按升序排second按降序排。所以second1>second2，意味着first1>first2。代码来自discuss，二分法部分我改成了我习惯的模式。
https://leetcode.com/discuss/106939/c-time-o-nlogn-space-o-n-similar-to-lis-nlogn-solution
bool cmp (pair<int, int> i, pair<int, int> j) {
if (i.first == j.first)
return i.second > j.second;
return i.first < j.first;
}
class Solution {
public:
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
int N = envelopes.size();
vector<int> candidates;
sort(envelopes.begin(), envelopes.end(), cmp);
for (int i = 0; i < N; i++) {
int lo = 0, hi = candidates.size();
while (lo < hi) {
int mid = lo + (hi - lo)/2;
if (envelopes[i].second > envelopes[candidates[mid]].second)
lo = mid + 1;
else
hi = mid;
}
if (lo == candidates.size())
candidates.push_back(i);
else
candidates[lo] = i;
}
return candidates.size();
}
};
