优于网上博客(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;

    }

};

};