Given an integer array
nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.Example:
<strong>Input:</strong> [-2,1,-3,4,-1,2,1,-5,4], <strong>Output:</strong> 6 <strong>Explanation:</strong> [4,-1,2,1] has the largest sum = 6.
解法:
class Solution: def maxSubArray(self, nums: 'List[int]') -> 'int': if not nums: return 0 curSum = maxSum = nums[0] for num in nums[1:]: curSum = max(num, curSum + num) maxSum = max(maxSum, curSum) return maxSum
说明:
cursum是计算累加的数值和 与当前的数值大小之间的最大值,如果过去遍历的数据的累加和都没有现在的值大,那么过去累加的数据都没有任何的意义
maxsum就是不断的计算cursum的最大值,返回最终的结果