codeforces-Ed88-D

D. Yet Another Yet Another Task

题意

长度为n的数组a 其中-30<=ai<=30

要求找到“区间和-区间最大值”的最大值
数组中包含负数
因为答案最小为 0
所以可以从 1 到 30 枚举可能的区间最大值
然后遍历寻找最大子段和
如果遍历到位置 i 时，前一段子段和小于 0 ，说明已经不是最优解，此时置nowsum为 0
如果遍历到位置 i 时，位置 i 的值 a[i] > 枚举出的区间最大值 mx ，此时不符假设，说明第 i 个位置不可取，nowsum置 0
/*
或者将原数组中大于mx的数置为负无穷

假设最大值L,R 在某个大于mx的数的左边
那么他会被nowsum 记录
假设最大值L,R 跨越某个大于mx的数
那么这个nowsum非法 因为假设L,R中的最大值为mx
这等效于某段nowsum<0则删去该子段从当前数后一个数重新开始统计一个子段类似
由于子段可以为空那么nowsum不会小于0所以若某个数设为ai使得当前的连续子段和小于0
那么这个数一定不会被包括在最终取最大sum值的子段中
假设某子段[L,j]包括这个ai那么子段和sum[L~j]=sum[L~i]+sum[i+1~j]
sum[L~i]<0那么显然sum[i+1~j]>sum[L~j] 所以直接抛弃[L~i]从i+1开始从新统计sum和

其次为什么枚举到的区间中最大值若不存在也不会得到错误答案
由ans-mx构成的函数图像是
ans
| /
| / | / |
| / | / | / |
| / | / | / |
| |/ | / |
| |/ |
|————————–> mx

(用txt画图╮(╯▽╰)╭)

当mx枚举到区间中确实存在的数时函数会存在一个极值点
其他不存在的mx都会被更新掉 最后取max的值实际上都是极值点在比较

*/

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

# include <bits/stdc++.h>

using namespace std;
typedef long long ll;

# define endl '\n'

# define Turnoff std::ios::sync_with_stdio(false)

const ll Max=1e5+5;
const int inf=1e8;
int data[Max];
int main(){
    Turnoff;
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>data[i];
    int sum=0;
    for(int num=0;num<=30;num++){
        int now=0;
        for(int i=1;i<=n;i++){
            now+=data[i];
            if(now<0||data[i]>num)now=0;
            sum=max(now-num,sum);
        }
    }
    cout<<sum<<endl;
}