最大子数组之和

题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

输入一个整型数组num,数组中一个或连续的多个整数组组成一个子数组,求所有子数组的和的最大值。

参考: LeetCode 53.Maximum Subarray

Example

Input: [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: 子数组[4, -1, 2, 1]拥有最大和6

分析

举例分析数组规律

首先,因为数组中有正有负,那么最后得到的最大和一定大于0。我们试着对例子中的数组逐个累加:

  1. 初始化和为0
  2. 加上num[0] -2,和为-2
  3. 加上num[1] 1,和为-1,更新最大和为-1
  4. 加上num[2] -3,和为-4,因为-4比之前的最大和还要小,所以把-1保存起来
  5. 加上num[3] 4,和为0。由于之前的最大和为-1,加上4之后得到0比4本身还要小。也就是说从num[0]开始的子数组的和会小于从num[3]开始的子数组的和,因此我们舍弃掉之前的和,直接从num[3]开始累加。
  6. 加上num[4] -1,和为3,我们发现此时的和比之前的4小,因此把之前的和4保存起来,它有可能为最大和
  7. 加上num[5] 2,和为5,大于之前保存的和4,因此更新最大和为5
  8. 加上num[6] 1,和为6,6大于5,同理更新最大和为6
  9. 加上num[7] -5,和为1,因为num[7]小于0,所以和之前一样,将之前的最大和6保存起来
  10. 加上num[8] 4,和为5,这是数组的最后一个元素,而5小于6,因此最终的最大子数组之和为6,对应的子数组为[4, -1, 2, 1]

代码实现

以下为Python3的实现:

1
2
3
4
5
6
7
class Solution:
def maxSubArray(self, num):
curSum = maxSum = num[0]
for num in nums[1:]:
curSum = max(num, curSum + num)
maxSum = max(curSum, maxSum)
return maxSum