# 53. Maximum Subarray 最大子序和

## 刷题内容

• https://leetcode.com/problems/maximum-subarray
• https://leetcode-cn.com/problems/maximum-subarray

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



## 解题方案

O(N^2)

class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
m = float('-inf')
for i in range(n):
s = 0
for j in range(i,n):
s = s + nums[j]
m = max(m,s)
return m


• 动态规划（只关注：当然值 和 当前值+过去的状态，是变好还是变坏，一定是回看容易理解）
• ms(i) = max(ms[i-1]+ a[i],a[i])
• 到i处的最大值两个可能，一个是加上a[i], 另一个从a[i]起头，重新开始。可以AC
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
maxSum = [nums[0] for i in range(n)]
for i in range(1,n):
maxSum[i] = max(maxSum[i-1] + nums[i], nums[i])
return max(maxSum)


start:
max_so_far = a[0]
max_ending_here = a[0]

loop i= 1 to n
(i) max_end_here = Max(arrA[i], max_end_here+a[i]);
(ii) max_so_far = Max(max_so_far,max_end_here);

return max_so_far



AC代码：

class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
maxSum , maxEnd = nums[0], nums[0]

for i in range(1,n):
maxEnd = max(nums[i],maxEnd + nums[i])
maxSum = max(maxEnd,maxSum)
return maxSum


class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def find_max_crossing_subarray(nums, low, mid, high):
left_sum = float('-inf')
sum = 0
for i in xrange(mid,low-1,-1):
sum = sum + nums[i]
if sum > left_sum:
left_sum = sum

right_sum = float('-inf')
sum = 0
for j in range(mid+1,high+1):
sum = sum + nums[j]
if sum > right_sum:
right_sum = sum

return left_sum + right_sum

def find_max_subarray(nums,low,high):
if low == high:
return nums[low]
else:
mid = (low + high) / 2
left_sum = find_max_subarray(nums, low, mid)
right_sum = find_max_subarray(nums,mid+1,high)
cross_sum = find_max_crossing_subarray(nums,low,mid,high)
# print left_sum, right_sum, cross_sum
# print mid, low, high
return max(left_sum, right_sum, cross_sum)

return find_max_subarray(nums, 0, len(nums)-1)