优于网上博客(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;
    }
};
};
已邀请:

要回复问题请先登录注册

返回顶部