LeetCode题解之Longest Increasing Subsequence

1、题目描述

2、题目分析

使用动态规划，在计算以每个字符结尾的最长子序列。

3、代码

int lengthOfLIS(vector<int>& nums) {
        if(nums.size() == 0){
            return 0;
        }
        
        vector<int> dp(nums.size() , 1);
        int maxans = 1;
        for(int i = 1; i < nums.size(); i++){
            int maxval = 0;
            for( int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    maxval = max(dp[j], maxval);
                }
            }
            dp[i] = maxval + 1;
            maxans = max(dp[i], maxans);
        }
        
        return maxans;
    }