题目描述
- 方法一：动态规划
这里设定
f
(
n
)
f(n)
f(n)为包含当前第
n
n
n个数num的最大连续子数组和，则可以写出递推公式为
f
(
n
)
=
max
(
n
u
m
,
f
(
n
−
1
)
+
n
u
m
)
f
(
0
)
=
n
u
m
s
[
0
]
f(n) = max(num, f(n-1)+num)\ f(0) = nums[0]
f(n)=max(num,f(n−1)+num)f(0)=nums[0]
注意这里递推公式中不是
f
(
n
)
=
max
(
f
(
n
−
1
)
,
f
(
n
−
1
)
+
n
u
m
)
f(n) = max(f(n-1), f(n-1)+num)
f(n)=max(f(n−1),f(n−1)+num)
因为要保证是连续数组和
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_subarray = nums[0]
res = nums[0]
for num in nums[1:]:
max_subarray = max(num, max_subarray + num)
res = max(res, max_subarray)
return res
