子数组的最大累加和

分类: 文章 • 2024-09-24 12:12:40

注：子数组连续，子序列不连续

arr=[5,2,-6,2,4]
cur=0
maxx=float("-inf")
for i in range(len(arr)):
    cur+=arr[i]
    maxx=max(cur,maxx)
    cur=max(0,cur)
print(maxx)

两个假设：
（1）累加和最大
（2）累加和最大中最长的数组

（0，L-1）累加和一定不是正的
（L，Z）累加和一定不是负的
子数组的最大累加和