首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【leetcode刷题】T165-最长上升子序列

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

作者头像
木又AI帮
发布2019-09-17 14:26:34
3900
发布2019-09-17 14:26:34
举报
文章被收录于专栏:木又AI帮木又AI帮

木又连续日更第1天(1/100)

木又的第165篇leetcode解题报告

动态规划类型第10篇解题报告

leetcode第300题:最长上升子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/

【题目】

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

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

说明:

可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。

【思路】

这是一道很正常的动态规划题目:dp[i] = max(dp[j] + 1),这里的第j个元素需要满足条件nums[j] < nums[i]

【代码】

python版本

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)

C++版本

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;
    }
};
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-09-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 木又AI帮 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档