C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2021-09-10

class AscentSequence {
public:
    int findLongest(vector<int> nums, int n) {
        if(n==1){
            return 1;
        }
        //vector<int> dp(n+1); //dp[i]表示以i结尾的最长递增子序列长度
        vector<int> ends; //ends[i]表示以i长度的递增子序列的最小值结尾,如果有比它大的就扩容
        //dp[0] = 1;
        int cur=0;
        ends.push_back(nums[0]);
        for(int i=1;i<n;i++){
            if(nums[i]<ends[cur]){
                //ends[cur] = nums[i];
                int j = lower_bound(ends.begin(),ends.end()+cur,nums[i]) - ends.begin(); //二分法在ends中查找第一个大于nums[i]的值
                //二分查找恰好合适的位置
                ends[j] = nums[i];
                //dp[i] = dp[i-1];
            }else{
                ends.push_back(nums[i]);
                cur++;
                //dp[i] = dp[i-1]+1;
            }

        }
        return cur+1;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2022-02-05

class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        // write code here
        vector<int> dp(n+1, 0);
        if (n == 0) return 0;
        
        int maxlen = 1;
        dp[1] = A[0];
        
        for (int i = 1; i < n; ++i) {
            /*if (A[i] > dp[maxlen]) {
                dp[++maxlen] = A[i];
            } else {
                auto index = upper_bound(dp.begin()+1, dp.begin()+1+maxlen, A[i]);
                *(index) = A[i];
            }*/
            auto pos = upper_bound(dp.begin()+1, dp.begin()+maxlen+1, A[i]);
            if (pos == dp.begin()+maxlen+1) {
                dp[++maxlen] = A[i];
            } else {
                *pos = A[i];
            }
        }
        return maxlen;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 420KB, 提交时间: 2021-12-15

class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        int dp[n];
        int help[n];
        int max_length=0,count=0;
        dp[0]=1;help[0]=A[0];
        for(int i=1;i<n;i++)                             //遍历数字序列
            {
            int right=count,left=0,middle;
            while(left<=right){ //   查找A[i]更新help[]时的位置
                middle=(left+right)/2;
                if(A[i]>=help[middle]){
                    left=middle+1;
                }else{
                    right=middle-1;
                }
            }
            help[left]=A[i];                        //更新help[]的值
            if(left>count)
                count=left;
            dp[i]=left+1;                     //更新dp[]的值
            if(dp[i]>max_length)       //更新最长递增子序列的长度
                max_length=dp[i];
        }
        return max_length;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 424KB, 提交时间: 2022-01-05

class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        if(n<=1)
            return n;
        int*dp=new int[n+1];
        dp[1]=A[0];
        int index=1;
        int left,right,middle;
        for(int i=1;i<n;++i){
            if(A[i]>dp[index])
                dp[++index]=A[i];
            else{
                left=1,right=index;
                while(left<=right){
                    middle=(left+right)/2;
                    if(A[i]>dp[middle])
                        left=middle+1;
                    else if(A[i]<dp[middle])
                        right=middle-1;
                    else
                        break;
                }
                if(left>right){
                    dp[left]=A[i];
            }
        }
        }
        delete[]dp;
        return index;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 432KB, 提交时间: 2022-05-17

class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        // write code here
        if (n == 0) return 0;
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (ans.empty() || ans.back() < A[i]) {
                ans.push_back(A[i]);
            }
            else {
                int pos = lower_bound(ans.begin(), ans.end(), A[i]) - ans.begin();
                ans[pos] = A[i];
            }
        }
        return ans.size();
    }
};