当前位置：网站首页>【动态规划】最长递增子序列

【动态规划】最长递增子序列

2022-04-23 06:11:00 【小风_】

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

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

定义： d p [ i ] dp[i] dp[i]示从0到 i i i为止最长的递增子序列

边界条件： d p [ i ] = 1 ， i dp[i]=1，i dp[i]=1，i​​​从​ 0 0 0到 N − 1 N-1 N−1

状态转移方程： d p [ i ] = m a x ( d p [ j ] ) + 1   ,   i f    n u m s [ i ]   >   n u m s [ j ] dp[i] = max(dp[j])+1~,~if ~~nums[i]~>~nums[j] dp[i]=max(dp[j])+1 , if  nums[i] > nums[j]​

说明：​每一个索引号位 i i i​​的为止的最长递增子序列，等于遍历从0到i为止的dp值的最大，同时该最大值对应的数值要比索引号i数值要小

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

在查找最大的dp的时候，可以利用二分查找优化，使得O(nlogn)

版权声明
本文为[小风_]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_33952811/article/details/119106111

边栏推荐

猜你喜欢

随机推荐