题目大意：给一个有n个元素的a数组，可以选择其中一个区间的所有数都乘上x，也可以不选，求最大子序列和。
如果没有前面的操作，就是只求最大子序列和，我们都知道就一个贪心的思路，当目前序列的和<0了，我们就当它为0，因为它对后面的序列只有负的贡献，完全不会使和增大，只会使和减少。所以我们从左往右，和从右往左，分别处理出没有乘x的最大子序列和maxl和maxr，这样的话，如果我们在区间[l,r]内乘x，那么相应的答案就是(sum[r]-sum[l-1])*x+maxr[r+1]+maxl[l-1],emmm那天晚上我就推到了这，后面怎么枚举区间就不懂了，写了个尺取，但很明显不对，因为没有根据去调整区间。看了我们qdcxk的博客后领悟，还是一种贪心的思想。我们把前面的答案转化成sum[r]*x+maxr[r+1]-(sum[l-1]*x-maxl[l-1]),这样的话
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 typedef long long ll; 5 int a[301108]; 6 ll sum[301108],maxl[301108],maxr[301108]; 7 int main() 8 { 9 int n,x,y; 10 scanf("%d%d",&n,&x); 11 for(int i=1;i<=n;i++) 12 { 13 scanf("%d",&a[i]); 14 sum[i]=sum[i-1]+a[i]; 15 } 16 for(int i=1;i<=n;i++) 17 { 18 maxl[i]=maxl[i-1]+a[i]; 19 if(maxl[i]<0) 20 maxl[i]=0; 21 } 22 for(int i=n;i>=1;i--) 23 { 24 maxr[i]=maxr[i+1]+a[i]; 25 if(maxr[i]<0) 26 maxr[i]=0; 27 } 28 ll ans=0,minl=0; 29 for(int i=1;i<=n;i++) 30 { 31 minl=min(minl,sum[i]*1ll*x-maxl[i]);//先更新minl,就把不选的情况也包含了 32 ans=max(ans,maxr[i+1]+sum[i]*1ll*x-minl); 33 } 34 printf("%lld\n",ans); 35 return 0; 36 }
qdcxk还有个dp的做法，先挂上一发k神博客mmk27，没看懂，等k神给我讲明白了再更。