Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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?
Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int> dp(nums.size(), 1); int res = 0; for (int i = 0; i < nums.size(); ++i) { for (int j = 0; j < i; ++j) { if (nums[i] > nums[j]) { dp[i] = max(dp[i], dp[j] + 1); } } 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 0; vector<int> ends{nums[0]}; for (auto a : nums) { if (a < ends[0]) ends[0] = a; else if (a > ends.back()) ends.push_back(a); else { int left = 0, right = ends.size(); while (left < right) { int mid = left + (right - left) / 2; if (ends[mid] < a) left = mid + 1; 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 = 0; i < nums.size(); ++i) { int left = 0, right = dp.size(); while (left < right) { int mid = left + (right - left) / 2; if (dp[mid] < nums[i]) left = mid + 1; 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(); } };
本文转自博客园Grandyang的博客，原文链接：最长递增子序列[LeetCode] Longest Increasing Subsequence ，如需转载请自行联系原博主。