我要招人

去企业版

首页 > 试题广场 >

子数组的最大累加和问题

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

热度指数：85502 时间限制：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 3

传说中的2东东幺

class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        res = float('-inf')
        count = 0
        for i in range(len(arr)):
            count += arr[i]
            res = max(res,count)
            if count < 0:
                count = 0
        return res

贪心算法，累加计数，一旦遇到和小于0直接丢弃，重新开始计算。

发表于 2021-10-19 20:49:20 回复(0)

Python 3

昊天明月

class Solution:
def maxsumofSubarray(self , arr ):
# write code here
s :int = 0
maxs : int = 0
for i in arr:
s += i
if s<0:
s = 0
else:
maxs = max(maxs,s)
return maxs

发表于 2021-09-11 15:45:06 回复(0)

Python 3

牛客257319613号

#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        s_max = max(arr[0], 0)
        sub_max = arr[0]
        for v in arr[1:]:
            sub_max += v
            if sub_max <= 0 :
                sub_max = 0
            if s_max < sub_max:
                s_max = sub_max
        return s_max

发表于 2021-09-06 23:13:50 回复(0)

Python 3

牛客362805906号

class Solution:
    def maxsumofSubarray(self , arr ):
        sum=0
        ans=0
        length=len(arr)
        for i in range(len(arr)):
            sum+=arr[i]
            if sum>ans:
                ans=sum
            if sum<0:
                sum=0
        return ans

发表于 2021-09-05 09:38:24 回复(0)

Python 3

可恶，被他装到了

#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
def maxsumofSubarray(self , arr ):
maxvalue = 0
temp = 0
for i in arr:
if temp + i < 0:
temp = 0
else:
temp += i
if temp > maxvalue:
maxvalue = temp
return maxvalue
# write code here

发表于 2021-08-24 12:29:53 回复(0)

Python 3

求求求offerofferoffer

#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
def maxsumofSubarray(self , arr ):
# write code here
# 第一步：初始化最大值为第一个元素，累加值为0
maxsum = arr[0]
tmpsum = 0
for i in arr:
# 第二步：遍历元素：如果累加值小于0，则累加值赋予当前元素，否则继续累加
if tmpsum < 0:
tmpsum = i
else:
tmpsum = tmpsum + i
# 第三步：判断累加值与最大值，如果比最大值大，则最大值为当前累加值
if tmpsum > maxsum:
maxsum = tmpsum
return maxsum

发表于 2021-08-16 15:00:40 回复(0)

Python 3

牛客944262486号

class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        tmp, res = 0, 0
        for i in range(len(arr)):
            if arr[i] > 0: tmp += arr[i]
            else: tmp = max(0, res+arr[i])
            if tmp > res: res = tmp
        return res

发表于 2021-08-14 21:38:34 回复(0)

Python 3

我有班上啦

class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        max_arr = []
        max_sum = 0
        for i in arr:
            if  max_sum < 0:
                max_sum = i
            else:
                max_sum += i
            max_arr.append(max_sum)
        max_sum = max(max_arr)
        return max_sum

设置一个累加和列表max_arr和一个最大值max_sum,每进行一步首先判断最大值max_sum是否小于0，如果小于0的话就将当前数组中的数i赋值给max_sum，每循环一次将当前最大值放入累加和列表中，全部循环完毕后求累加和列表Max_arr中的最大值

发表于 2021-08-13 10:39:46 回复(0)

Python 3

Stephenling

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

发表于 2021-08-10 22:03:08 回复(0)

Python 3

TURBOTX

#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxsumofSubarray(self , arr ):
        #特殊情况
        if(len(arr)<1):
            return 0
        #普通情况
        sumRes=arr[0]     #初始状态
        maxNum=sumRes     #存储临时较大值
        #转移状态方程
        for i in range(1,len(arr)):
            if(sumRes>0):
                sumRes = sumRes + arr[i]
            else:
                sumRes = arr[i]
            maxNum=max(maxNum,sumRes)
        return maxNum

发表于 2021-08-05 13:58:25 回复(0)

Python 3

王钲超

class Solution:
def maxsumofSubarray(self , arr ):
global_max = 0
max_cache = 0
for i in arr:
max_cache = max(0, i + max_cache)
if global_max < max_cache:
global_max = max_cache
return global_max

发表于 2021-07-25 17:11:49 回复(0)

Python 3

dingx92

写法一：O(n); O(n)

class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        n = len(arr)
        if n==1:
            return arr[0]
        dp = [0]*n 
        dp[0] = arr[0]
        for i in range(1,n):
            if dp[i-1]<0:
                dp[i] = arr[i]
            else:
                dp[i] = dp[i-1]+arr[i]
        return max(dp)

写法二：滚动数组，O(n); O(1)

class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        n = len(arr)
        if n==1:
            return arr[0]
        res, cur = arr[0], arr[0]
        for i in range(1,n):
            cur = max(cur+arr[i], arr[i])
            res = max(res, cur)
        return res

编辑于 2021-07-14 20:19:55 回复(0)