【線上程式設計産品介紹】
阿裡雲開發者社群線上程式設計：
免費刷題大神器，助你拿到好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月份比賽正式開啟！機械鍵盤等你拿！