打卡群刷题总结0924——最长上升子序列

木又AI帮

发布于 2020-09-28 16:36:16

2930

发布于 2020-09-28 16:36:16

文章被收录于专栏：木又AI帮

题目：300. 最长上升子序列

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

给定一个无序的整数数组，找到其中最长上升子序列的长度。示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

解题：

1、dp问题。公式为：dp[i] = max(1, dp[i - j] +1)，其中，nums[i - j] < nums[i]。

代码：

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-09-25，如有侵权请联系 cloudcommunity@tencent.com 删除