LeetCode 53. Maximum Subarray

题目

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

分析

最大子数组和问题

  • 输入:一个数组
  • 任务:找出子数组的最大和
  • 输出:最大和(注意,不需要找出数组,只需要求最后的最大和)

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution:
# @param A, a list of integers
# @return an integer
def max_subarray(self, nums):
if not nums:
return 0
local_sum = max_sum = nums[0]
for num in nums[1:]:
local_sum = max(num, local_sum + num)
global_sum = max(global_sum, local_sum)
return max_sum

解释

首先考虑数组为空的特殊情况,直接返回0,然后设置两个变量局部最大值和全局最大值;遍历数组,比较 local_sum 和 cur_sum+num 大小,更新 local_sum,然后比较 local_sum 和 global_sum,更新 global_sum。