Interview Classic 150 Questions P300 Longest Increasing Subsequence

---

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 \le j < i , nums[j] < nums[i])} + 1;$$

#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

#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());
        }
};