【剑指offer】面试题42. 连续子数组的最大和
2021-01-09 11:32
标签：原来 问题 分析 http span off css pre lse 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 对于示例，通过分析发现，对于累加的子数组和，如果大于零，继续累加就行；否则，则需要剔除原来的累加和重新开始。输出一直是最大值 当前待输入 当前累加子数组和 max -2 -2删 -2 1 1 1 -3 -2 删 1 4 4 4 -1 3 4 2 5 5 1 6 6 -5 1 6 4 5 6 【剑指offer】面试题42. 连续子数组的最大和 标签：原来 问题 分析 http span off css pre lse 原文地址：https://www.cnblogs.com/fuj905/p/12961125.html问题描述
面试题42. 连续子数组的最大和
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。分析
解题
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
#累加的子数组和，如果大于零，那么我们继续累加就行；否则，则需要剔除原来的累加和重新开始
if(len(nums) == 0):
return None
curmax=nums[0]
resmax=nums[0]
for i in nums[1:]:
if curmax >0:
curmax += i
else:
curmax =i
if curmax > resmax:
resmax = curmax
return resmax
文章标题：【剑指offer】面试题42. 连续子数组的最大和
文章链接：http://soscw.com/index.php/essay/41157.html