给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
解题思路：
1、贪心算法
关键在于，每次要将当前和和最大和比较产生最大和，体现了贪心的思想；
是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
时间复杂度：O(n)
代码：
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans=nums[0]
sum1=0
for i in range(len(nums)):
if sum1>0:
sum1=sum1+nums[i]
else:
sum1=nums[i]
ans=max(ans,sum1)
return ans
2、动态规划
关键在于，后一个元素的值只由前一个元素决定，体现了动态规划的思想；
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(1,len(nums)):
if nums[i-1]>0:
nums[i]=nums[i-1]+nums[i]
return max(nums)
网友评论