LeetCode300：最长递增子序列

题目描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列

代码

/*
    dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

    递推公式
    if(nums[i]>nums[j])
        dp[i] = max(dp[j]+1,dp[i])
    
    初始化
        dp[i] = 1

    遍历顺序
        for(int i=0;i<nums.size();i++)
            for(int j=0;j<i;j++)
                
       
*/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;

        vector<int> dp(nums.size(), 1);
        
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};



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