Cover image for Top Interview 150 P300 Longest Increasing Subsequence

Top Interview 150 P300 Longest Increasing Subsequence

(Updated: )
algorithm
, , ,
Timeline

Timeline

2025-12-12

init

Dynamic Programming

Problem:

P300 Longest Increasing Subsequence

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

dp[i]=max(dp[j])(0≤j<i,nums[j]<nums[i])+1;dp[i] = max(dp[j])_{( 0 \le j < i , nums[j] < nums[i])} + 1; 

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] is the length of the longest strictly increasing subsequence ending with 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());
        }
};

leetcode hot 100 rewrite

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <vector>
#include <algorithm>

using std::vector;

class Solution {
    public:
        int lengthOfLIS(vector<int> &nums)
        {                
                int i, j, n = nums.size();

                // dp[i] represents the length of the longest increasing subsequence ending with nums[i]
                vector<int> dp(n, 1);

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