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?
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), );
int res = ;
for (int i = ; i < nums.size(); ++i) {
for (int j = ; j < i; ++j) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + );
}
}
res = max(res, dp[i]);
}
return res;
}
};
下面来看一种优化时间复杂度到 O(nlgn) 的解法，这里用到了二分查找法，所以才能加快运行时间哇。思路是，先建立一个数组 ends，把首元素放进去，然后比较之后的元素，如果遍历到的新元素比 ends 数组中的首元素小的话，替换首元素为此新元素，如果遍历到的新元素比 ends 数组中的末尾元素还大的话，将此新元素添加到 ends 数组末尾(注意不覆盖原末尾元素)。如果遍历到的新元素比 ends 数组首元素大，比尾元素小时，此时用二分查找法找到第一个不小于此新元素的位置，覆盖掉位置的原来的数字，以此类推直至遍历完整个 nums 数组，此时 ends 数组的长度就是要求的LIS的长度，特别注意的是 ends 数组的值可能不是一个真实的 LIS，比如若输入数组 nums 为 {4, 2， 4， 5， 3， 7}，那么算完后的 ends 数组为 {2， 3， 5， 7}，可以发现它不是一个原数组的 LIS，只是长度相等而已，千万要注意这点。参见代码如下：
解法二：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return ;
vector<int> ends{nums[]};
for (auto a : nums) {
if (a < ends[]) ends[] = a;
else if (a > ends.back()) ends.push_back(a);
else {
int left = , right = ends.size();
while (left < right) {
int mid = left + (right - left) / ;
if (ends[mid] < a) left = mid + ;
else right = mid;
}
ends[right] = a;
}
}
return ends.size();
}
};
我们来看一种思路更清晰的二分查找法，跟上面那种方法很类似，思路是先建立一个空的 dp 数组，然后开始遍历原数组，对于每一个遍历到的数字，用二分查找法在 dp 数组找第一个不小于它的数字，如果这个数字不存在，那么直接在 dp 数组后面加上遍历到的数字，如果存在，则将这个数字更新为当前遍历到的数字，最后返回 dp 数组的长度即可，注意的是，跟上面的方法一样，特别注意的是 dp 数组的值可能不是一个真实的 LIS。参见代码如下：
解法三：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp;
for (int i = ; i < nums.size(); ++i) {
int left = , right = dp.size();
while (left < right) {
int mid = left + (right - left) / ;
if (dp[mid] < nums[i]) left = mid + ;
else right = mid;
}
if (right >= dp.size()) dp.push_back(nums[i]);
else dp[right] = nums[i];
}
return dp.size();
}
};
下面来看两种比较 tricky 的解法，利用到了 C++ 中 STL 的 lower_bound 函数，lower_bound 返回数组中第一个不小于指定值的元素，跟上面的算法类似，还需要一个一维数组v，然后对于遍历到的 nums 中每一个元素，找其 lower_bound，如果没有 lower_bound，说明新元素比一维数组的尾元素还要大，直接添加到数组v中，跟解法二的思路相同了。如果有 lower_bound，说明新元素不是最大的，将其 lower_bound 替换为新元素，这个过程跟算法二的二分查找法的部分实现相同功能，最后也是返回数组v的长度，注意数组v也不一定是真实的 LIS，参见代码如下：
解法四：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> v;
for (auto a : nums) {
auto it = lower_bound(v.begin(), v.end(), a);
if (it == v.end()) v.push_back(a);
else *it = a;
}
return v.size();
}
};
既然能用 lower_bound，那么 upper_bound 就耐不住寂寞了，也要出来解个题。upper_bound 是返回数组中第一个大于指定值的元素，和 lower_bound 的区别时，它不能返回和指定值相等的元素，那么当新进来的数和数组中尾元素一样大时，upper_bound 无法返回这个元素，那么按算法三的处理方法是加到数组中，这样就不是严格的递增子串了，所以要做个处理，在处理每个新进来的元素时，先判断数组v中有无此元素，有的话直接跳过，这样就避免了相同数字的情况，参见代码如下：
解法五：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> v;
for (auto a : nums) {
if (find(v.begin(), v.end(), a) != v.end()) continue;
auto it = upper_bound(v.begin(), v.end(), a);
if (it == v.end()) v.push_back(a);
else *it = a;
}
return v.size();
}
};
还有一种稍微复杂点的方法，参见我的另一篇博客 Longest Increasing Subsequence，那是 LintCode 上的题，但是有点不同的是，那道题让求的 LIS 不是严格的递增的，允许相同元素存在。
Github 同步地址：
https://github.com/grandyang/leetcode/issues/300
类似题目：
Increasing Triplet Subsequence
Number of Longest Increasing Subsequence
Minimum ASCII Delete Sum for Two Strings
参考资料：
https://leetcode.com/problems/longest-increasing-subsequence/