力扣：300.最长递增子序列

力扣：300.最长递增子序列

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

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

解析：
这其实是一个递归题目，dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度，从0~i-1找到小于当前值的值同时其dp又是所有满足这个情况里面最大的，只需要将这个的dp+1即是当前值的最大上升子序列长度。
代码：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() == 1) return 1;
        vector<int>dp(nums.size(),1);
        int result = 0;
        for(int i = 1; i < nums.size(); ++i){
            for(int j = 0; j < i; ++j){
                if(nums[i] > nums[j]) dp[i] = max(dp[i],dp[j]+1);
            }
            result = dp[i] > result?dp[i]:result;
            //if (dp[i] > result) result = dp[i]; // 取长的子序列
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16