最大子段和
给定一个整数序列 $a[0],a[1],...,a[n-1]$，你可以选择 $k$ 个位置加 $x$，使得最大子段和最大。你需要对于每个 $0\le k\le n$，求出最大子段和的最大值。
最大子段和定义为选择 $0\le l\le r\le n,a[l]+a[l+1]+...+a[r-1]$（选择 $l=r$ 时即为 $0$）的最大值。
$1\le n \le 5000,0\le x\le 10^5,\lvert a[i]\rvert\le 10^5$。
输入格式：
第一行两个整数 $n,x$。
第二行 $n$ 个整数 $a[0],a[1],...,a[n-1]$。
输出格式：
$n+1$ 行，第 $i$ 行一个整数，表示 $k=i-1$ 时的答案。
输入样例：

3 5
-2 -7 -1

输出样例：

0
4
4
5

提示：假设固定 $k$，对于一对 $l,r$，最大的和为 $a[l]+a[l+1]+...+a[r-1]+\min(k,r-l)\times x$。枚举 $k$，对于 $r-l\le k$ 和 $r-l\gek$ 的分别计算最大值即可。
程序：

#include<bits/stdc++.h>
using namespace std;
int n,x,a[5000],sum[5001],ans[5001];

int main(){
	cin>>n>>x;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++)
		sum[i+1]=______ ①_______;
	for(int l=0;l<=n;l++)
		for(int r=l;r<=n;r++)
			ans[r-l]=max(ans[r-l],________ ②_______);
	for(int i=1;i<=n;i++)
		ans[i]=max(ans[i],________ ③_______);
	for(int k=0;k<=n;k++){
		int pre_min=0;
		for(int i=k;i<=n;i++){
			pre_min=min(pre_min,________ ④_______);
			ans[k]=max(ans[k],________ ⑤_______);
		}
	}
	for(int i=0;i<=n;i++)
		cout<<ans[i]<<endl;
	return 0;
}

---

(1) ①处应填写（ ）

A. sum[i]+a[i]
B. sum[i+1]+a[i]
C. a[i]
D. sum[i]+a[i+1]

(2) ②处应填写（ ）

A. sum[r]-sum[l]
B. sum[r]-sum[l]+(r-l)*x
C. sum[r]-sum[l]+r*x
D. ans[r]-ans[l]

(3) ③处应填写（ ）

A. sum[i]
B. ans[i-1]+x
C. a[i-1]
D. ans[i-1]

(4) ④处应填写（ ）

A. ans[i-k]
B. ans[i]
C. sum[i-k]
D. sum[i]

(5) ⑤处应填写（ ）

A. k*x-pre_min
B. sum[i]-pre_min+k*x
C. ans[i]-pre_min-(i-k)*x
D. ans[i]-pre_min+k*x

---

我目前做的是 1.A 2.B 3.D 4.? 5.C。第 4 小问完全没有思路，这套题目没有答案QAQ，希望大家伸出援手。