优于网上博客(4行核心代码AC)： LeetCode 300. Longest Increasing Subsequence
最长公共子序列有O(n^2)的常见写法，还有O(n*logn)的二分写法详细见博客 （ http://blog.csdn.net/jmspan/ar ... 71519 ）
我AC完发现O(n * logn)的算法网上没有用把内层循环抽象成可以用C++ stl实现的代码，所以发下我的供大家参考，快速AC
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
int ans = 1;
cache[0] = nums[0];
vector<int> cache(10000, INT_MAX);
for (int i = 1; i < n; ++i){
int pos = lower_bound(cache.begin(), cache.begin() + n, nums[i]) - cache.begin();
cache[pos] = nums[i];
if (pos == ans) ans++;
}
return ans;
}
};
};
0 个回复