leetcode-300-线性DP-最长上升子序列

发表于 | 分类于

题目

2.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 动态规划，O（n^2）
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        // dp[i] 表示以第i个数字结尾的最长上升子序列
        vector<int> dp(n, 1);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < i; ++j)
                if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
            
        return *max_element(dp.begin(), dp.end());
    }
};

// 动态规划 + 二分查找
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        // dp[i] 表示每一个最长上升子序列对应末位数字的最小数值
        vector<int> dp(n, 0);
        for(int num : nums){
            int i = 0, j = res;
            while(i < j){
                int m = i + (j - i) / 2;
                if(dp[m] < num) i = m + 1;
                else j = m;
            }
            dp[i] = num;
            if(res == j) ++res;
        }

        return res;
    }
};