题意：
给你一个包含 n 个元素的序列 a[]；
定义序列 a[] 的 beauty 为序列 a[] 的连续区间的加和最大值，如果全为负数，则 beauty = 0；
例如：
a[] = {10, -5, 10, -4, 1} ;
beauty = 15;( 10+(-5)+10 )
a[] = {-3, -5, -1};
beauty = 0;( 不取 )
给你一个整数 x，你可以将序列 a[] 的任意子序列 a[ l , r ]*x（即 a[l]=a[l]*x,a[l+1]=a[l+1]*x,.....,a[r]=a[r]*x）；
当然，也可以不执行这个操作；
求 beauty 的最大值；
思路：
一看到这道题，第一反应就贪过去了；
贪了好大一会，交了几发程序，全部 "Wrong answer on test 5"；
看了一眼他人的AC代码，看到了 dp 数组，然后，想了好久好久的动态规划解法；
wa 了改，改了 wa，终于，在下午临近吃饭的时候，AC了（大佬轻点虐）
假设修改的区间为[ L,R ]
那么，对于∀i∈[1,n], i = L or L < i < R or i = R；
定义 dp[ i ][ j ]，含义如下：
j = 0 : i 作为修改区间的起始位置，从 i 开始向左能形成的最大区间和；
j = 1 : i 作为修改区间的中间位置，从 i 开始向左能形成的最大区间和；
j = 2 : i 作为修改区间的终点位置，i 可以形成的最大区间和；
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INFll 0x3f3f3f3f3f3f3f3f
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=3e5+; int n,x;
ll a[maxn];
/**
在做*x的操作下
dp[i][0]:i位置为修改区间的开始
dp[i][1]:i位置为修改区间的中间部分
dp[i][2]:i位置为修改区间的结尾
*/
ll dp[maxn][];
/**
在不做*x的操作下
maxL[i]:以i开始的向左能形成的最大的区间和
maxR[i]:以i开始的向右能形成的最大的区间和
*/
ll maxL[maxn];
ll maxR[maxn]; ll Solve()
{
maxL[]=-INFll;
for(int i=;i <= n;++i)
maxL[i]=max(maxL[i-]+a[i],a[i]);
maxR[n+]=-INFll;
for(int i=n;i >= ;--i)
maxR[i]=max(maxR[i+]+a[i],a[i]); dp[][]=dp[][]=;
for(int i=;i <= n;++i)
{
dp[i][]=x*a[i]+(maxL[i-] > ? maxL[i-]:);
dp[i][]=max(dp[i-][],dp[i-][])+x*a[i];
dp[i][]=max(dp[i][],dp[i][])+(maxR[i+] > ? maxR[i+]:);
} ll ans=;
for(int i=;i <= n;++i)
ans=max(max(ans,maxL[i]),dp[i][]); return ans;
}
int main()
{
while(~scanf("%d%d",&n,&x))
{
for(int i=;i <= n;++i)
scanf("%lld",a+i);
printf("%I64d\n",Solve());
}
}
巨巨代码（额外增加点我的注释）
#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long int n,x;
ll a[];
ll dp[][]; int main()
{
ll ans=;
cin>>n>>x;
for(int i=;i<=n;++i)
cin>>a[i]; mem(dp[],);
/**
dp[i][0]:[1,i]未使用*x所形成的最大区间和
dp[i][1]:[L,i-1]使用*x，并且i也使用*x所形成的最大区间和
dp[i][2]:[L,i-1]使用*x，但是i不使用*x所形成的最大区间和
*/
for(int i=;i<=n;++i)
{
dp[i][]=a[i]+(dp[i-][] > ? dp[i-][]:);
dp[i][]=max(0LL,max(dp[i-][],dp[i-][]))+a[i]*x;
dp[i][]=max(0LL,max(dp[i-][],dp[i-][]))+a[i];
for(int j=;j<;++j)//三者去最值
ans=max(ans,dp[i][j]);
}
cout<<ans<<endl; return ;
}