Yet Another Yet Another Task

Created by LXC on Tue Oct 17 08:52:00 2023

https://codeforces.com/problemset/problem/1359/D

ranting: 2000

tag: data structures, dp, implementation, two pointers

problem

给出一个数组a，寻找[l,r]区间，使得sum(a[l...r])-max(a[l...r])最大。

a的取值在[-30,30]

solution

对于区间中最大元素为x，那么我们将所有大于x的元素改为负无穷。这样做是为了保证区间不会包含大于x的元素。

然后我们预处理出l[]和r[]数组，其中l[i]代表以a[i]作为区间右端点的最大子段和，r[i]代表以a[i]作为区间左端点的最大子段和。

我们遍历a中元素，若a[i] == x。那么包含a[i]且不包含大于a[i]的区间的最大字段和为max(l[i-1],0)+a[i]+max(r[i+1],0)，这个区间的最大值为a[i]，我们移除它便可作为答案的贡献。

总时间复杂度为$O(n \max a_i)$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i:a) cin >> i;
    int ans = 0;
    for (int b=30; b>=0; b--) {
        for (int i=0; i<n; i++) {
            if (a[i] > b) a[i] = -60;
        }
        vector<int> l(n), r(n);
        l[0] = a[0];
        for (int i=1; i<n; i++) {
            l[i] = max(0, l[i-1]) + a[i];
        }
        r[n-1] = a[n-1];
        for (int i=n-2; i>=0; i--) {
            r[i] = max(0, r[i+1]) + a[i];
        }
        for (int i=0; i<n; i++) {
            if (a[i] == b) {
                ans = max(ans, (i-1>=0?max(0, l[i-1]):0)+(i+1<n?max(0, r[i+1]):0));
            }
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}