动态规划专题

02/20/2024 - 01

300. 最长递增子序列

• 给定一个列表，求出最长递增子序列的长度。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        lens = len(nums)
        # 定义dp[i]为以index=i结尾的最长子序列的长度
        dp = [1] * lens

        for i in range(lens):
            for j in range(i):
                if nums[i] > nums[j]:
                    # 状态转移方程
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)

02/20/2024 - 02

152. 乘积最大子数组

• 给定一个列表，求乘积最大的连续子数组的乘积。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxF, minF, res = nums[0], nums[0], nums[0]
        lens = len(nums)
        for i in range(1, lens):
            mx = maxF
            mn = minF

            # 因为涉及到数值正负号的问题，所以需要同时记录i-1位置为结尾的子数组的乘积的最大值和最小值
            maxF = max(mx * nums[i], max(nums[i], mn * nums[i]))
            minF = min(mx * nums[i], min(nums[i], mn * nums[i]))

            res = max(maxF, res)
        
        return res