文章目录
-
- 1 问题描述
- 2 示例
- 3 题解
- 4 Python3代码实现
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