最大子段和

给定一个整数序列a[0],a[1],...,a[n-1],你可以选择k个位置加x，使得最大子段和最大。你需要对于每个0≤k≤n,求出最大子段和的最大值。

最大子段和定义为选择0≤1≤r≤n, a[l]+a[l+1]+...+a[r-1] (选择l=r时即为0)的最大值。

1≤n≤5000, 0≤x≤10^5,|a[il|≤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-1)*x.

枚举k,对于r-1<=k和r-1>=k的分别计算最大值即可。

程序:

#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]=__(1)__;


	for (int l=0; l<=n; ++l)


		for(int r=1; r<=n; ++r)


			ans[r-1] = max(ans[r-1], __(2)__);


	for (int i=1; i<=n; ++i)


		ans[i] = max (ans[i], __(3)__);


	for (int k=0; k<=n; ++k){


		int pre_min =0;


		for (int i=k; i<=n; ++i){


				pre_min = min(pre_min, __(4)__);


				ans[k] = max(ans[k],__(5)__);


		}


	}


	for (int i=0; i<=n; ++i) cout << ans[i]<<"\n";


}

选择题