力扣题解300.最长递增子序列

思路看注释

O（n ^ 2）

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int dp[nums.size()]; // dp[i] 表示到达第i个数字的最长递增子序列长度
        int ma = -1; //全局答案
        for (int i = 0; i < nums.size(); i++) {
            dp[i] = 1; //数组初始化
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j] ) dp[i] = max(dp[i], dp[j] + 1); // 状态转移
            }
            ma = max(ma, dp[i]); // 全局答案更新
        }
        return ma;
    }
};

O（nlogn）

class Solution {
public:    
    int lengthOfLIS(vector<int>& nums) {
        
        int ans[nums.size()]; //把递增子序列存储在ans, 一个有序的数组
        int t = 0; //t表示元素数量，也就是答案
        for (int i = 0; i < nums.size(); i++) {
            if (t && ans[t - 1] >= nums[i]) {
                // 二分答案 00000111111类型
                int l = 0, r = t - 1;
                while (l < r) {
                    int mid = (l + r) >> 1;
                    if (ans[mid] < nums[i]) l = mid + 1;
                    else r = mid;
                }
                ans[l] = nums[i];
            } else ans[t++] = nums[i];
        }
        return t;
    }
};