问题来自LeetCode300

dp[i]表示以第i位结尾的长度，则状态转移方程dp[i] = max(d[j] + 1) && i > j && nums[i] > nums[j]
初值 dp[i] = 1，时间复杂度O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size(), ret = 1;
        vector<int> dp(len, 1); 
        
        if (len == 0)
            return 0;
        
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]);
        }
        
        return ret;
    }
};