难度: Easy
原题连接
内容描述
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******
从i开始，计算i到n，存比较大的sum，会超时
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
思路 2 - 时间复杂度: O(NlgN)- 空间复杂度: O(N)******
参见clrs 第71页，用divide and conquer，有伪码
最大的subarray sum有三个可能，左半段或者右半段，或者跨越左右半段,
速度比较慢，AC代码，复杂度O(NlogN)
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)
思路 3 - 时间复杂度: O(N)- 空间复杂度: O(N)******
- 动态规划（只关注：当然值 和 当前值+过去的状态，是变好还是变坏，一定是回看容易理解）
- 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)思路 4 - 时间复杂度: O(N)- 空间复杂度: O(1)******
Kadane’s Algorithm wikipedia可以查到,然后一般的是负的可以还回0，这里需要稍作修改，参考
http://algorithms.tutorialhorizon.com/kadanes-algorithm-maximum-subarray-problem/
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
"""
max_sum, max_end = nums[0], nums[0]
for i in range(1, len(nums)):
max_end = max(max_end + nums[i], nums[i])
max_sum = max(max_sum, max_end)
return max_sum