300. Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input:[10,9,2,5,3,7,101,18]Output: 4 Explanation: The longest increasing subsequence is[2,3,7,101], therefore the length is4.
Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
给定一个数组，求最长上升子序列（Longest Increasing Subsequence, LIS）的长度。子序列可以是不连续的，和子串不一样。
此题有两种解法，一种$O(n^2)$，另一种$O(nlgn)$。
先来看$O(n^2)$。设length[i]表示到nums[i]时的LIS，那么此时已知了length[0,…,i-1]，对于$j\in[0,…,i-1]$，如果nums[i]>nums[j]，则在i处的LIS至少是length[j]+1，因为可以在nums[j]后面接nums[i]，构成LIS，所以在i处的LIS加一。我们尝试所有的$j\in[0,…,i-1]$，找一个最大的length[j]+1赋给length[i]。
递推式如下：
length(i) = max { length(j) + 1 : if nums[j] < nums[i] }
0≤j≤i-1
这种思路的代码如下，因为需要两层循环，所以时间复杂度为$O(n^2)$。
class Solution {
public:
int lengthOfLIS(vector<int>& nums)
{
int n = nums.size();
if (n < 1)
return 0;
vector<int> length(n, 1);
int ans = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
length[i] = max(length[i], length[j] + 1);
}
}
ans = max(ans, length[i]);
}
return ans;
}
};本代码提交AC，用时33MS。
接下来看看$O(nlgn)$的解法。
对于数组d（代码中的数组nums的简称），我们定义一个辅助数组B，B[j]保存了到目前为止LIS=j时的最后一个数的最小的数，比如B[3]=8表示到目前为止长度为3的上升子序列的最后一个数的最小值为8。我们不断更新B的长度和数值，最后B的长度就是最长的上升子序列的长度，但是数组B并不是一个LIS。
举例说明。假设数组下标从1开始。数组d=[3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12]，初始时B的长度为1，且B[1]=3表明此时最长上升子序列的长度为1，且该LIS的最后一个数的最小值是3。
d[2]=5，因为d[2]>B[1]，所以5可以加入最长上升子序列，导致此时的最长上升子序列长度为2，且最后一个数的最小值就是5，所以B[2]=5。此时B[1]=3不变，因为长度为1的LIS的末尾数值还是3不变。B=[3,5]。
d[3]=6，同上，d[3]>B[2]，所以6也加入最长上升子序列，导致LIS=3，且B[3]=6。B=[3,5,6]。
d[4]=2，注意此时d[4]<B[3]，所以2不能增加以B[3]=6结尾的最长上升子序列，所以数组B的长度不变。查找B，发现2比B[1]=3小，所以替换B[1]=3为B[1]=2，此含义为长度为1的LIS的末尾最小数由3变更为2。这很好理解，因为2自身可以作为一个LIS，且比3自身作为LIS要小。B=[2,5,6]。
d[5]=5，同上，d[5]<B[3]，查找B，更新B[2]=5，因为B[2]本身就是5，所以更新前后一样。B=[2,5,6]。
d[6]=4，d[6]<B[3]，无法增长最长上升子序列，查找B，发现4在B[1]=2和B[3]=6之间，更新B[2]=4，含义为长度为2的LIS的最后一个数的最小值由5更新为4。B=[2,4,6]。其实这样更新的目的就是为了把各个长度的LIS的末尾的最小数变小，使得后续的数更有可能接在之前LIS的末尾来增加LIS的长度。
d[7]=19，d[7]>B[3]，贡献LIS长度，直接加入数组B，即B[4]=19。B=[2,4,6,19]。
d[8]=5，查找B，在4,19之间，所以更新B[3]=5。B=[2,4,5,19]。
d[9]=6，查找B，更新B[4]=6。B=[2,4,5,6]。
d[10]=7，d[10]>B[4]，贡献LIS长度，直接加入数组B，即B[5]=7。B=[2,4,5,6,7]。
d[11]=12，d[11]>B[5]，贡献LIS长度，直接加入数组B，即B[6]=12。B=[2,4,5,6,7,12]。
以上算法过程涉及到在数组B中查找当前元素d[i]的替换位置，因为数组B是有序的，所以可以使用二分查找，最终算法的时间复杂度降为了O(nlgn)。
STL中自带了在有序数组中二分查找的函数，lower_bound输入为一个数组B和目标target，返回数组B中不小于target的最小下标。我们也可以自己用二分查找实现。
这种思路的代码如下：
class Solution {
public:
int lowerbound(vector<int>& B, int target)
{
int l = 0, r = B.size() – 1;
while (l < r) {
int m = (l + r) / 2;
if (B[m] == target)
return m;
else if (B[m] > target)
r = m – 1;
else
l = m + 1;
}
return B[l] < target ? (l + 1) : l;
}
int lengthOfLIS(vector<int>& nums)
{
int n = nums.size();
if (n < 1)
return 0;
vector<int> B = { nums[0] };
for (int i = 1; i < n; ++i) {
if (nums[i] > B.back())
B.push_back(nums[i]);
else {
//*lower_bound(B.begin(), B.end(), nums[i]) = nums[i];
B[lowerbound(B, nums[i])] = nums[i];
}
}
return B.size();
}
};本代码提交AC，用时3MS，速度一下提高了不少。
参考：
- http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html#3
- https://www.felix021.com/blog/read.php?1587
二刷。第二种解法，可以直接调stl的lower_bound，最好自己写，和 http://code.bitjoy.net/2020/03/21/leetcode-find-first-and-last-position-of-element-in-sorted-array/ 这题代码FindFirstIndex一致，记住二分搜索的标准写法。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0)return 0;
vector<int> curmin;
for (int i = 0; i < n; ++i) {
if (curmin.empty() || nums[i] > curmin.back()) {
curmin.push_back(nums[i]);
}
else {
//vector<int>::iterator it = lower_bound(curmin.begin(), curmin.end(), nums[i]);
//*it = nums[i];
int l = 0, r = curmin.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (nums[i] <= curmin[m]) {
r = m - 1;
}
else {
l = m + 1;
}
}
curmin[r + 1] = nums[i];
}
}
return curmin.size();
}
};
本代码提交AC，用时8MS。