题解 | #最长上升子序列(一)#

class Solution {
public:
    int dp[1005]={0};//dp[i]表示以arr[i]为结尾的严格上升子序列的长度
    int LIS(vector<int>& arr) {
        int n=arr.size();
        int res=0;//初始化
        for(int i=0;i<n;i++){//遍历每个arr[i]
            dp[i]=1;//初始化为1
            for(int j=0;j<i;j++){
                if(arr[j]<arr[i])//确保严格上升
                    dp[i]=max(dp[i],dp[j]+1);
            }
            res=max(res,dp[i]);//维护最大值
        }
        return res;
    }
};

class Solution {
public:
    int dp[1005]={0};//dp[i]存储的长度为i+1的尽可能小的值
    int LIS(vector<int>& arr) {
        int n=arr.size();
        if(n==0)
            return 0;
        int len=0;//初始化
        dp[len++]=arr[0];//初始化
        for(int i=1;i<n;i++){//遍历每个arr[i]
            if(arr[i]>dp[len-1]){//如果严格大于dp[]的最后一个数，则加入dp[]
                dp[len++]=arr[i];
            }else{//否则，二分找到dp[]中>=arr[i]的数，并用arr[i]替换
                int l=0,r=len-1,mid;
                while(l<r){
                    mid=(l+r)>>1;
                    if(dp[mid]>=arr[i]){
                        r=mid;
                    }else{
                        l=mid+1;
                    }
                }
                dp[l]=arr[i];//替换
            }
        }
        return len;
    }
};