leetcode300：最长递增子序列

题目链接

leetcode

题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

/*
    状态表示：
        f[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
    状态计算：
        f[i] = max(f[i], f[j]) + 1，
        a[j] < a[i]，其中 j = 1, 2, ..., i-1

    时间复杂度：O(n^2)
        状态数*转移数 = O(n*n) = O(n^2)
    空间复杂度：O(n)
        数组需要空间 O(n)。
*/
class Solution_0 {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1); // 初始化为 1

        // 状态计算
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
        }
        
        int k = 0;
        // 找到递增子序列的最大长度
        for (int i = 0; i < n; i++) {
            if (f[k] < f[i]) {
                k = i;
            }
        }

        return f[k];
    }
};

/*  
    思路同上

    时间复杂度：O(n^2)
    空间复杂度：O(n)
*/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 1); // 初始化为 1
        int res = 0;

        // 状态计算
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            // 更新最长递增子序列的长度
            res = max(res, f[i]);
        }

        return res;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> test_cases = {
        {10,9,2,5,3,7,101,18},
        {0,1,0,3,2,3},
        {7,7,7,7,7,7,7}
    };

    for (auto& nums : test_cases) {
        cout << "Input: ";
        for (int num : nums) {
            cout << num << " ";
        }
        cout << endl;
        cout << "Output: " << solution.lengthOfLIS(nums) << endl;
    }

    return 0;
}