【在线编程产品介绍】

阿里云开发者社区在线编程：

免费刷题大神器，助你拿到好offer

周赛月赛不停歇，做题还能领奖品

大赛笔试全真题，常做常新有惊喜

点击链接开始产品体验：https://developer.aliyun.com/coding

本文为大家介绍的是“124.Codancer的求和”的解法探究。先来看一下题目内容：

题目详情

等级：困难
知识点：线段树
查看题目：Codancer的求和

现在Codancer有两个长度均为n的数组a数组和b数组，其中对于a中的每个元素a[i]都有(-10^6<=a[i]<=10^6)，对于b中的每个元素b[i]都有(0<=b[i]<=n)，对于每个i(1<=i<=n)，我们定义区间[L,R]是合法的只有[L,R]满足下面的条件：
1、1<=L<=R<=n
2、0<=i-L,R-i<=b[i]

现在对于每个i,Codancer想找到一组合法区间使得(a[L]+a[L+1]+...a[R])最大，并将这个最大值记为s[i]。

现在请计算(s[1]+s[2]+s[3]+...+s[n])。

输入包含一个n(1<=n<=10^5)和两个数组b,a。(b在前面，a在后面)

输出s数组的和。

示例1
输入：
5
[1,2,3,4,4]
[-5,1,2,3,-4]
输出：
16

注意:
s[1]=-4
s[2]=6
s[3]=6
s[4]=6
s[5]=2
因此最终答案为16

解题思路

S[1]=a[1]+a[2]=-4，此时S[1]最大
S[2]=a[2]+a[3]+a[4]=6,此时S[2]最大
同理可得
S[3]=a[2]+a[3]+a[4]=6, S[4]=a[2]+a[3]+a[4], S[5]=a[2]+a[3]+a[4]+a[5]=2
因此答案为S[1]+S[2]+S[3]+S[4]+S[5]=16。

考虑对a数组做前缀和数组pre,即pre[i]是(a[1]+a[2]+...+a[i])的值，同时对a做后缀和数组sa,即sa[i]是(a[i]+a[i+1]+...a[n])的值，那么s[i]可以由两部分组成，左边的a[L]+...+a[i]，右边的a[i]+...+a[R]。

左边其实就是找到一个L，使得a[L]+...+a[i]尽可能的大，右边同理,因此左边其实就是max(sa[max(1,i-k)]...sa[i])-sa[i+1]。

右边是max(pre[i]...pre[min(i+k,n)])。

对前缀和和后缀和分别建立线段树，O(log(n))求解s[i]即可，答案会爆int,因此需要用long long存储。

看完之后是不是有了答题思路了呢，快来练练手吧：124.Codancer的求和

在线编程周赛、月赛火热进行中，更有限时答题活动，定制卫衣、双肩背包、机械键盘等多重好礼等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程3月份比赛正式开启！机械键盘等你拿！