问题描述:
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
时间超限： 暴力穷举
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
""" max = nums[0]
if len(nums) == 1:
return nums[0]
res = 0
for step in range(len(nums)):#step 控制连续加的个数
for i in range(len(nums)-step):#i控制从第几个开始加
for j in range(step+1):
res += nums[i]
i += 1
if res > max:
max = res
res = 0
return max
方法1：当前值的大小与前面的值之和比较，若当前值更大，则取当前值，舍弃前面的值之和
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
preSum = maxSum = nums[0]
for i in xrange(1, len(nums)):
preSum = max(preSum + nums[i], nums[i])
maxSum = max(maxSum, preSum)
return maxSum
方法2：（分治法）对半分，求左边最大，右边最大，以及边界最大 ，返回最大值
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def maxSum(alist, left, right):
#递归返回条件
if left >= right:
return alist[left] #return原值，不是return 0 middle = (left + right) // 2 #记得打括号，去（TiMe）调了老半天
leftMax = maxSum(alist, left, middle)
rightMax = maxSum(alist, middle+1, right) #求左边界最大值
leftBoardSum, leftBoardMax = 0, alist[middle]
for i in range(middle, left-1,-1): #左段最右端没有取到middle
leftBoardSum += alist[i]
if leftBoardSum > leftBoardMax:
leftBoardMax = leftBoardSum #求右边界最大值
rightBoardSum, rightBoardMax = 0, alist[middle+1]
for j in range(middle+1, right+1): #右段最右端取到了right
rightBoardSum += alist[j]
if rightBoardSum > rightBoardMax:
rightBoardMax = rightBoardSum #边界最大值
boardMax = leftBoardMax + rightBoardMax return max(leftMax, rightMax, boardMax) if nums == []:
return 0 left = 0
right = len(nums)-1
res = maxSum(nums, left, right) #left,right为左右下标
return res
2018-07-24 11:11:59