当前位置：首页 > article >正文

[leetcode]300_最长递增子序列

article 2024/10/2 12:52:41

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：
你能将算法的时间复杂度降低到 O(n log(n)) 吗?

解题思路：【动态规划】

    dp[i]表示num[i]结尾的最长递增子序列长度
    dp[i] = max(dp[i], dp[j] + 1)
        当 nums[i]>nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j]+1 ；
        当 nums[i]<=nums[j] 时： nums[i] 无法接在 nums[j] 之后，此情况上升子序列不成立，跳过。
    初始化dp[i] = 1

class Solution:
    def longest_substring_dp(self, nums):
        length = len(nums)
        dp = [1] * length
        for i in range(1, length):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
if __name__ == '__main__':
    num = eval(input())
    solution = Solution()
    print(solution.longest_substring_dp(num))

仅作为代码记录，方便自学自查自纠

查看全文

http://www.kler.cn/news/328888.html