扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
给定一个整数数组 nums ，找到一个具有大和的连续子数组（子数组最少包含一个元素），返回其大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
思路：
首先我们分析题目，我们思考，为什么大和的连续子数组不包含其他的元素而是这几个呢？因为如果我们想在现有的基础上去扩展当前连续子数组，相邻的元素是一定要被加入的，而相邻元素中可能会减损当前的和。
思路一：
遍历法，On:
算法过程：遍历数组，用onesum去维护当前元素加起来的和。当onesum出现小于0的情况时，我们把它设为0。然后每次都更新全局大值。
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
#onesum维护当前的和
onesum = 0
maxsum = nums[0]
for i in range(len(nums)):
onesum += nums[i]
maxsum = max(maxsum, onesum)
#出现onesum<0的情况，就设为0，重新累积和
if onesum < 0:
onesum = 0
return maxsum
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网