【leetcode刷题】T165-最长上升子序列

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 2:
            return len(nums)
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            for j in range(i-1, -1, -1):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() < 2)
            return nums.size();
        vector<int> dp(nums.size(), 1);
        int res = 1;
        for(int i=1; i<nums.size(); i++){
            for(int j=i-1; j >= 0; j--){
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};