1 问题描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

2 示例

输入：[-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6

3 题解

我们用动态规划的思路来解决该问题：

对数组进行遍历，用sum记录遍历到当前元素时，前面若干个连续子序列的最大和；用ans来存储最终的结果。sum和ans的初值都为数组的第一个元素

• 若sum > 0，则sum产生增益效果，保留sum并加上当前遍历元素
• 若sum <= 0，则sum无增益效果，则舍弃sum并令sum等于当前元素，重新计算收益
• 每次遍历，都将sum和ans进行比较，若sum > ans，则将ans的值更新为sum

这里有一种比较形象的方式来理解动态规划：

假设你是一个选择性遗忘的赌徒，数组表示你这几天来赢钱或者输钱。
你用sum来表示之前几天来的输赢，用ans来存储你手里赢到的最多的钱.

• 如果昨天你手上还是输钱（sum < 0），你忘记它，从今天重新开始算起；
• 如果昨天你手上还是赢钱（sum > 0），你记得它，加上今天的战绩；
• 及时更新ans，存储sum的最大值。

4 Python3代码实现

def maxSubArray(nums):
	sum = nums[0]
	ans = nums[0]
	for i in range(1,len(nums)):
		if sum > 0:
			sum += nums[i]
		else:
			sum = nums[i]
		if sum > ans:
			ans = sum  
	return ans