最大连续区间和（带负值）
You are given an arrayaaconsisting ofnnintegers. Beauty of array is the maximum sum of someconsecutive subarrayof this array (this subarray may be empty). For example, the beauty of the array[10, -5, 10, -4, 1]is15, and the beauty of the array[-3, -5, -1]is0.
You may chooseat most one consecutive subarrayofaaand multiply all values contained in this subarray byxx. You want to maximize the beauty of array after applying at most one such operation.
The first line contains two integersnnandxx(1≤n≤3⋅105,−100≤x≤1001≤n≤3⋅105,−100≤x≤100) — the length of arrayaaand the integerxxrespectively.
The second line containsnnintegersa1,a2,…,ana1,a2,…,an(−109≤ai≤109−109≤ai≤109) — the arrayaa.
Print one integer — the maximum possible beauty of arrayaaafter multiplying all values belonging to some consecutive subarrayxx.
5 -2 -3 8 -2 1 -6
22
12 -3 1 3 3 7 1 3 3 7 1 3 3 7
42
5 10 -1 -2 -3 -4 -5
0
In the first test case we need to multiply the subarray[-2, 1, -6], and the array becomes[-3, 8, 4, -2, 12]with beauty22([-3,8, 4, -2, 12]).
In the second test case we don't need to multiply any subarray at all.
In the third test case no matter which subarray we multiply, the beauty of array will be equal to0.
题意 ： 让你选择一段区间，将区间中的每个值乘以X，求此时的最大区间和
思路分析 ：
比赛的时候想了一个做法，X若为正数，就是正常的求个最大区间和*X，但若是非正数时，当时想的是找到整个序列中最大连续的负的区间和将其乘以X再加上区间的左右俩个端点分别向倆端可以扩展到的最大连续整数和，这个预处理一下就行，WA掉了，后面想明白了
假设答案是某段区间最终要乘以X，那么最终答案会是 sum[l, r]*x+qian[l-1]+hou[r+1]
再做进一步的化简 sum[r]-sum[l-1]+qian[l-1]+hou[r+1] , 移项 sum[r]+hou[r+1]+(qian[l-1]-sum[l-1]) 那么只需要维护倆端的最大值即可
ll n, x;
ll a[maxn];
ll f[maxn];
ll qian[maxn], hou[maxn], sum[maxn];
void solve2(){
for(ll i = 1; i <= n; i++){
sum[i] += sum[i-1]+a[i];
}
ll last = n+1;
for(ll i = n; i >= 1; i--){
if (a[i] >= 0){
hou[i] = max(a[i]+sum[last-1]-sum[i]+hou[last], a[i]);
last = i;
}
}
ll first = 0;
for(ll i = 1; i <= n; i++){
if (a[i] >= 0){
qian[i] = max(a[i]+sum[i-1]-sum[first]+qian[first], a[i]);
first = i;
}
}
ll a1 = 0, a2 = 0;
ll ans = hou[1];
for(ll i = 1; i <= n; i++){
ll num = qian[i-1]-x*sum[i-1];
a1 = max(a1, num);
ll num2 = x*sum[i]+hou[i+1]+a1;
ans = max(ans, num2);
}
printf("%lld\n", ans);
}
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> x;
for(ll i = 1; i <= n; i++){
scanf("%lld", &a[i]);
}
solve2();
return 0;
}
正解应该是做个DP，
dp[i][0] 表示以 i 位置为结尾的最大连续区间和是多少；
dp[i][1] 表示 i 位置 * X 的最大连续区间和是多少
dp[i][2] 表示 i 位置是 a[i]，但其前面有一段是乘过X的，此时的最大连续区间和
代码示例：
ll n, x;
ll a[maxn];
ll dp[maxn][3];
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> x;
ll ans = 0;
for(ll i = 1; i <= n; i++){
scanf("%lld", &a[i]);
dp[i][0] = max(dp[i-1][0]+a[i], a[i]);
dp[i][1] = max(a[i]*x+max(dp[i-1][0], dp[i-1][1]), a[i]*x);
dp[i][2] = max(a[i]+max(dp[i-1][1], dp[i-1][2]), a[i]);
ll f = max(dp[i][0], max(dp[i][1], dp[i][2]));
ans = max(ans, f);
}
cout << ans << endl;
return 0;
}
优质内容筛选与推荐>>1、c#皮肤美化：MainForm窗体
2、期望问题（转）
3、Linux 开放服务端口
4、SQL SERVER小Tips
5、排查http post时遇到的问题