Description
求 \(l,r\) 使得 \(\sum_{l \le i \le r} a_i - \max_{l \le i \le r} a_i\) 最大化。\(|a_i| \le 30\)
Solution
考虑枚举删除的数的大小 \(val\),那么现在只有 \(a_i \le val\) 的数才是可用的,这样原序列就被分割成了若干段,选择不能跨段。
假如相邻的两个不可用位置是 \(p,q\),那么可用区间就是 \([p+1,q-1]\),在前缀和序列上的选择位置就是 \([p,q-1]\)。
我们考虑扫描固定一个左端点,右端点不断向右平移,如果累积和小于零则置为 \(0\),同时不断更新答案,遇到不可用点时,将累积和置为 \(0\) 并跳过。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> a(n+2);
for(int i=1;i<=n;i++) cin>>a[i];
int ans=0;
for(int val=0;val<=30;val++)
{
int sum=0;
for(int i=1;i<=n;i++)
{
if(a[i]>val)
{
sum=0;
}
else
{
sum+=a[i];
sum=max(sum,0);
ans=max(ans,sum-val);
}
}
}
cout<<ans<<endl;
}