【Leetcode | Python】53. 最大子数组和 [动态规划]

🚀总结

本题的核心在于维护一个列表 dp，列表中第 i 个元素表示以数组中第 i 个元素结尾的最大子数组和。

以数组中第 i 个元素结尾的最大子数组和，要么是元素 i 自身（前面的最大子数组和小于0），要么是元素 i-1 加上前面的最大子数组和（前面的最大子数组和大于0）

对于数组中第 i 个元素：

如果以数组中第 i-1 个元素结尾的最大子数组和大于0，则加上以前一个数字结尾的最大子数组和，使得当前数字结尾的最大子数组和更大，即

以数组中第 i 个元素结尾的最大子数组和 = 以数组中第 i-1 个元素结尾的最大子数组和 + 数组中第 i 个元素。
如果以数组中第 i-1 个元素结尾的最大子数组和小于0，则没有必要加上以前一个数字结尾的最大子数组和，“另起炉灶”，即

以数组中第 i 个元素结尾的最大子数组和 = 数组中第 i 个元素。

公式表示如下：

[

]

{

[

−

]

[

]

[

−

]

[

]

[

−

]

≤

dp[i] = \begin{cases} dp[i – 1] + nums[i], & \text{if } dp[i – 1] > 0 \\ nums[i], & \text{if } dp[i – 1] \leq 0 \end{cases}

dp[i]={dp[i−1]+nums[i],nums[i],if dp[i−1]>0if dp[i−1]≤0

📇题目

⭐思路

对于一个整数数组 nums，它所能构成的连续子数组非常多，直接遍历所有可能的连续子数组非常困难。因此需要将这个问题转化为很多个子问题，并且确保：① 解决所有的子问题能够确保解决原问题；② 子问题的求解之间存在联系，从而提高计算效率。

将 “最大连续子数组和” 的问题转化为 “以元素 i 结尾的最大连续子数组和” 的子问题，经过这种转化：

① 如果以

⋆

\text{i}^\star

i⋆ 结尾的最大连续子数组和是所有以 i(i = 1, 2, …, n) 结尾的最大连续子数组和中最大的那一个，那么以

⋆

\text{i}^\star

i⋆ 结尾的最大连续子数组和也是这个整数数组的最大子数组和；

② 以 i 结尾的最大连续子数组和与以 i-1 结尾的最大连续子数组和之间存在联系。

🛠️代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = []
        dp.append(nums[0])  # dp 列表的第一个元素为数组第一个元素
        for i in range(1, len(nums)):
            if dp[i - 1] > 0:  # 如果以前一个元素结尾的最大子数组和大于0
                dp.append(nums[i] + dp[i - 1])  # 以当前元素结尾的最大子数组和 = 以前一个元素结尾的最大子数组和 + 当前元素
            else:  # 如果以前一个元素的最大子数组和小于等于0
                dp.append(nums[i])  # 以当前元素结尾的最大子数组和 = 当前元素
        return max(dp)

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/a5a45bcd86.html