我要招人

去企业版

首页 > 试题广场 >

子数组的最大累加和问题

[编程题]子数组的最大累加和问题

热度指数：85501 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的数组 arr ，返回其中任意连续子数组的最大累加和

题目保证没有全为负数的数据

数据范围： $1 \le n \le 100000$ ，数组中元素值 $|val| \le 100$

要求：时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$

示例1

输入

[1, -2, 3, 5, -2, 6, -1]

输出

说明

[3,6]范围内的子数组之和最大，3+5-2+6=12

示例2

输入

[1]

输出

备注:

算法知识视频讲解

Python

牛客581205746号

测试用例全部通过：

class Solution:
def maxsumofSubarray(self , arr ):
# write code here
if len(arr)==0:
return -1
sum = 0
maxt = arr[0]
for e in arr:
if sum <=0:
sum = e
else:
sum += e
maxt = max([maxt,sum])
return maxt

发表于 2021-06-22 15:38:25 回复(0)

Python

牛客诶谁

class Solution:

def maxsumofSubarray(self , arr ):

if arr is None:

return None

elif len(arr) == 0:

return arr

elif len(arr) == 1:

return arr[0]

else:

arr[0] = max(arr[0], 0)

for i in range(1, len(arr)):

arr[i] = max(arr[i-1]+arr[i], 0)

return max(arr)

发表于 2021-04-24 15:45:59 回复(0)

Python

wengJJ

Python

遍历数组，只要累计和是负数就将累计和归零（累计和是负数证明对后面的累计和能否成为最大值是负面效应）

#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        total = 0
        maxi = arr[0]
        for i in range(len(arr)):
            total = total + arr[i]
            if total <= 0:
                total = 0
            elif total >= maxi:
                maxi = total 
        return maxi

发表于 2021-04-17 18:19:57 回复(0)

Python

猫牛

class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        res = 0
        acc = 0
        for a in arr:
            acc = max(a, acc+a)
            res = max(res, acc)
           
        return res

发表于 2021-04-14 00:44:56 回复(0)

Python

迷茫的花痴

class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        max_subarray = curr_subarray = arr[0]
        
        for num in arr[1:]:
            curr_subarray = max(num, curr_subarray + num)
            max_subarray = max(max_subarray, curr_subarray)
        return max_subarray

编辑于 2021-04-10 11:58:24 回复(0)

Python

Core123

for i in range(1, len(arr)):
    if arr[i-1]>0:arr[i]+=arr[i-1]
    return max(arr)

发表于 2021-03-04 18:22:31 回复(0)

Python

aaaaaa/aaa

我的思路是，把所有值，从左到右依次累加，把这个结果当成一条曲线，用曲线的最高点减去最低点，就是最大子数组和

class Solution:
def maxsumofSubarray(self , arr ):
# write code here
if len(arr)<2:
return arr[0]

low,high,tmp = arr[0],0,0
for i in arr:
tmp+=i
if tmp>high:
high = tmp
if tmp<low:
low = tmp
if low>0:
low = 0
return high-low

发表于 2021-03-01 21:42:25 回复(0)

Python

强人锁篮

class Solution:
    def maxsumofSubarray(self , arr ):
        ans = 0
        cum = 0
        for i in arr:
            cum += i
            if cum < 0:
                cum = 0
            elif cum > ans:
                ans = cum
        return ans

发表于 2021-01-28 20:59:18 回复(1)

Python

牛客924204077号

#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        a,b = 0,0
        for x in range(1,len(arr)):
            a = arr[x-1] + arr[x]
            b = arr[x]
            arr[x] = a if a>b else b
        return arr[-1]

编辑于 2020-10-04 20:04:43 回复(0)