有个长度为(2n-1)的序列，值域([-K,K])（整数），其中奇数位已经确定，偶数位可以任意钦定。
钦定值，最大化，最大子段和-最大非负段和。
(nle 5000)
吼题。
记最大子段和为(A)，最大非负段和为(A_0)。
首先，最优解一定是：选择(A)对应区间([L,R])，区间内的空位填(K)或(-1)，区间外的空位填(-1)。
证明：假设最优解中(A)的区间为([L,R])。
考虑(A_0)的候选区间：
如果被([L,R])包含，处理公共部分（用上面的策略）没有影响，处理非公共部分只对(A)有利。
如果不被包含，显然不可能真相交。此时：如果(A_0)大于([L,R])中任意非负段，那么可以将任意非负段调到不超过(A_0)。如果有能调到(A_0)的，那么它成为了(A_0)的另一个候选区间，变成上面的情况；如果不能调到，它们一定要尽力调整，则每段中的空位顶到(K)。
其次，(L=1+[a_1<0],R=2n-1-[a_{2n-1}<0])。
证明：假如最优解中(A)对应区间([L_1,R_1])，只考虑向左扩展。
如果将左边所有空位填(K)，对(A)的贡献是([L,L_1-1])的最大后缀和。又因为填到了(K)，所以几乎所有后缀和其实都非负，因此最大后缀和是整个的和（如果(L_1-1)被固定而且为负数则其作为开头的后缀和为负，不过此时(L_1-2)肯定可以钦定为(K)）。
考虑(A_0)的候选区间（不与([L_1,R_1])相交的）：(A)的增量一定大于等于调整后的它，自然大于等于调整后的它的增量。
然后就可以写出DP啦。设(f_{i,j})表示到点(i)填了(j)个(-1)，此时(A_0)最小值。写出来大概长成：(f_{i,j}=min_kmax(f_{k,j-1},g_{k,i-1}))，其中(g_{l,r})表示([l,r])中空位全填(K)此时最大非负区间和。
发现随着(k)增加，(f_{k,j-1})增，(g_{k,{i-1}})减。所以可以用个指针记个分界点，做到(O(n^2))。
ls的神仙做法：
先考虑整个序列被固定的位置全部为(K)，看看怎么填才可以使得答案最大。
枚举分成(i)段，每段肯定要尽量平均。然后列出(i)关于答案的式子，估计出最优答案大概在(sqrt{2n})处取到。
现在被固定的位置可以是其它数。猜个结论：(i)大概会比前面的情况更少一些。
于是在大概(sqrt{2n})范围内枚举(i)，算下(A_0)最大值最小是多少，具体二分后贪心（扫过去空位填(-1)或(K)。如果填(K)非负区间和大于限制则填(-1)否则填(K)。然后得到真实的段数(i')，和(i)比较）。
时间(O(nsqrt n lg nK))
using namespace std;
#include <bits/stdc++.h>
const int N=5005,INF=1e9;
int n,k;
int a[N];
int f[N][N],g[N][N];
int sum,ans;
int main(){
//freopen("in.txt","r",stdin);
//freopen("43.in","r",stdin);
freopen("max.in","r",stdin);
freopen("max.out","w",stdout);
scanf("%d%d",&n,&k);
for (int i=1;i<=n;++i){
scanf("%d",&a[i]);
sum+=a[i];
}
if (n==1){
printf("0
");
return 0;
}
sum+=(n-1)*k-min(a[1],0)-min(a[n],0);
for (int i=1;i<=n;++i){
int s=0,mx=0;
for (int j=i;j<=n;++j){
if (a[j]<0)
s=0;
else{
s+=a[j];
mx=max(mx,s);
}
g[i][j]=mx;
s+=k;
mx=max(mx,s);
}
}
memset(f,127,sizeof f);
f[1][0]=0;
for (int i=2;i<=n;++i){
int k=i-1;
for (int j=i-1;j>=1;--j){
/*
int tmp0=INT_MAX;
for (int k=1;k<i;++k)
tmp0=min(tmp0,max(f[k][j-1],g[k][i-1]));
*/
if (j==1)
f[i][j]=max(f[1][0],g[1][i-1]);
else{
// k=max(k,j);
while (k>j && f[k-1][j-1]>g[k-1][i-1])
--k;
while (k<i && f[k][j-1]<=g[k][i-1])
++k;
int tmp=INT_MAX;
if (k<i) tmp=min(tmp,f[k][j-1]);
if (k-1>=j && f[k-1][j-1]<INF) tmp=min(tmp,g[k-1][i-1]);
f[i][j]=tmp;
}
}
}
for (int i=1;i<=n;++i)
for (int j=0;j<i;++j)
ans=max(ans,(sum-(k+1)*j)-max(f[i][j],g[i][n]));
printf("%d
",ans);
return 0;
}