总结
本题的核心在于维护一个列表 dp，列表中第 i 个元素表示以数组中第 i 个元素结尾的最大子数组和。
以数组中第 i 个元素结尾的最大子数组和，要么是元素 i 自身（前面的最大子数组和小于0），要么是元素 i-1 加上前面的最大子数组和（前面的最大子数组和大于0）
对于数组中第 i 个元素：
如果以数组中第 i-1 个元素结尾的最大子数组和大于0，则加上以前一个数字结尾的最大子数组和，使得当前数字结尾的最大子数组和更大，即 以数组中第 i 个元素结尾的最大子数组和 = 以数组中第 i-1 个元素结尾的最大子数组和 + 数组中第 i 个元素。如果以数组中第 i-1 个元素结尾的最大子数组和小于0，则没有必要加上以前一个数字结尾的最大子数组和，“另起炉灶”， 即 以数组中第 i 个元素结尾的最大子数组和 = 数组中第 i 个元素。
公式表示如下：
d
p
[
i
]
=
{
d
p
[
i
−
1
]
+
n
u
m
s
[
i
]
,
if
d
p
[
i
−
1
]
>
0
n
u
m
s
[
i
]
,
if
d
p
[
i
−
1
]
≤
0
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 结尾的最大连续子数组和” 的子问题，经过这种转化： ① 如果以
i
⋆
\text{i}^\star
i⋆ 结尾的最大连续子数组和是所有以 i(i = 1, 2, …, n) 结尾的最大连续子数组和中最大的那一个，那么以
i
⋆
\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)
参考文章
您阅读本篇文章共花了：
发表评论