题目大意:给定一个数组，从这个数组中任取一个连续的子数组，找出最大的子数组的和。
使用dp，\(f[i]\)表示到数组第i个元素的时候的和的最大值，那么\(f[i] = max(f[i-1] + nums[i], nums[i])\)
class Solution(object):
def maxSubArray(self, nums):
def dp(nums):
n = len(nums)
f = [0 for _ in range(n)]
f[0] = nums[0]
for i in range(1, n):
f[i] = max(f[i-1] + nums[i], nums[i])
return max(f)
return dp(nums)
因为上面的f[i]只跟f[i-1]有关系，所有可以使用滚动数组降维,一维的滚动数组降维成常数项。
class Solution(object):
def maxSubArray(self, nums):
def dp(nums):
n = len(nums)
curr = nums[0]
ans = nums[0]
for i in range(1, n):
curr = max(curr + nums[i], nums[i])
if curr > ans:
ans = curr
return ans
return dp(nums)