时间轴

2025-12-12

init

题目：

P300 最长递增子序列

https://leetcode.cn/problems/longest-increasing-subsequence/?envType=study-plan-v2&envId=top-interview-150

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
#include <vector>
#include <algorithm>
#include <climits>
using std::vector;

class Solution {
    public:
        int lengthOfLIS(vector<int> &nums)
        {
                // dp[i] 以nums[i]结尾的最长严格递增子序列的长度
                // dp[i] = max{dp[j]}(nums[j]<nums[i] && j<i) + 1;
                int i, j, n = nums.size();
                int max_val = INT_MIN;
                vector<int> dp(n, 1);

                for (i = 0; i < n; i++) {
                        max_val = INT_MIN;
                        for (j = 0; j < i; j++) {
                                if (nums[j] < nums[i]) {
                                        max_val = std::max(max_val, dp[j]);
                                }
                        }
                        if (max_val != INT_MIN) {
                                dp[i] = max_val + 1;
                        }else{
                                dp[i] = 1;
                        }
                }
                return *std::max_element(dp.begin(), dp.end());
        }
};