用暴力，枚举一个修改的，算最大子段和，o(n)2的复杂度1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include<cstdio>
#include<iostream>
using namespace std;
int a[99999];
int s;int n,p;
int main(){
freopen("songfen.in","r",stdin);
freopen("songfen.out","w",stdout);
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int maxn=-9999999;
for(int i=1;i<=n;i++)
{
s=0;
for(int j=1;j<=n;j++)
{
s=s+(j!=i?a[j]:p);
maxn=max(s,maxn);
if(s<0)s=0;
}
}
printf("%d",maxn);
fclose(stdin);
fclose(stdout);
}