题解 | 最长递增子序列

#include <algorithm>
class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        // write code here
        //原版LIS：dp[i]代表以A[i]结尾的LIS的长度
        //优化版本：使用二分查找加贪心，dp[i]代表所有长度为i+1的上升子序列中最小的末尾元素值。例如dp[2]代表所有长度为3的上升子序列中末尾元素的最小值。
        //遍历数组nums[i]，每次在dp中查找第一个出现的大于等于nums[i]的位置，将其替换成nums[i];如果不存在这样的位置，则将nums[i]插入dp的末尾。dp是严格递增序列，由其性质或者反证法可知；
        //充分性：假设处理nums[i]时，在dp中找到了dp[j]第一个大于等于nums[i],那么dp[j-1]小于nums[i]，说明nums[i]可以添加到dp[j-1]元素所代表的递增子序列的末尾使得序列长度加一，也就对应着dp[j]的位置。
        //必要性：由于dp严格递增，那么每次nums[i]必须且只能更新dp中的一个位置。如果更新两个以上的位置则无法满足严格递增
    vector<int>dp;
    for(int i=0; i<n; i++)
    {
        //在dp中找到第一个大于等于A[i]的位置
        auto it=lower_bound(dp.begin(), dp.end(), A[i]);
        if(it!=dp.end())
            *it=A[i];
        else
            dp.push_back(A[i]);
    }
    return dp.size();
    }
};