子数组的最大累加和问题

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

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

给定一个数组arr，返回子数组的最大累加和

例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.

[要求]

时间复杂度为

，空间复杂度为

输入描述:

第一行一个整数N。表示数组长度
接下来一行N个整数表示数组内的元素

输出描述:

输出一个整数表示答案

示例1

输入

7
1 -2 3 5 -2 6 -1

输出

备注:

算法知识视频讲解

查看答案及解析

Python

毓毓子最可爱

n=int(input())
number_list=list(map(int,input().split()))
dp=[number_list[i] for i in range(len(number_list))]
for i in range(1,len(number_list)):
    dp[i]=max(dp[i],dp[i-1]+number_list[i])
print(max(dp))

令dp[i]表示第i个位置时的最大值，则有递推方程dp[i]=max(dp[i],dp[i-1]+number_list[i])(前一个最大值加上当前数字是否是最大的，比如如果number_list[i]是负数就可能不是最大，不断的取最大的进行更新）

编辑于 2021-06-11 08:39:29 回复(0)

Python

圣诞节的安徒生

N = eval(input())
ls = list(map(int, input().split()))
max_sum = 0 # 最大值
count = 0 # 累加和初始化
for i in range(len(ls)):
    if ls[i]+count > 0:
        count += ls[i]
        max_sum = max(max_sum, count) # 每次累加都更新最大值
    else:
        count = 0
print(max_sum)

最大子列和问题：一次遍历，累加和大于0就一直累加，期间用max函数来选择每次累加后的最大值，当累加和为0或为负值时，重置累加和为0继续遍历

发表于 2019-08-13 16:41:08 回复(0)