F

先跑一遍n^2的区间更新, 再只对以1为L或以n为R的区间去更新k < n - 1的答案. 不难证明若选取的区间不以1为L或以n为R, 更新k + 1时进行扩充区间比不扩充区间更优.

template<class T, size_t N>
class SpareTableMin {
public:
    vector<array<T, N>> st;
    vector<int> lo2;
    SpareTableMin(vector<T>& w) {
        int len = int(w.size());
        st.resize(len);
        lo2.resize(len + 1);

        for (int i = 0; i < len; i++) st[i][0] = w[i];
        for (int i = 2; i <= len; i++) lo2[i] = lo2[i >> 1] + 1;

        for (int k = 1; k <= N; k++) {
            for (int i = 0; i + (1 << k) <= len; i++) {
                st[i][k] = min(st[i][k - 1], st[i + (1 << k - 1)][k - 1]);
            }
        }
    }

    T query(int l, int r) {
        int k = lo2[r - l + 1];
        return min(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

void solve() {
    int n; in >> n;
    vector<ll> a(n + 1), s(n + 1);
    vector<ll> st(n + 1);
    for (int i = 1; i <= n; i++) {
        in >> a[i];
        s[i] += s[i - 1] + a[i];
        st[i] = a[i];
    }
    SpareTableMin<ll, 20> Sta(st);
    vector<ll> res1(n + 1), res2(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (i == 1 and j == n) continue;
            ll val = s[j] - s[i - 1];
            ll mn = LLONG_MAX;
            if (i != 1) mn = min(mn, Sta.query(1, i - 1));
            if (j != n) mn = min(mn, Sta.query(j + 1, n));
            int len = j - i + 1;
            res1[len] = max(res1[len], val - mn);
        }
    }

    for (int i = 1; i < n; i++) {
        ll val = s[n] - s[i];
        int len = n - i;
        res2[len] = max(res2[len], val - a[i]);
        val = s[i];
        len = i;
        res2[len] = max(res2[len], val - a[i + 1]);
    }


    for (int i = 1; i < n - 1; i++) res2[i] = max(res2[i], res2[i - 1]);
    for (int i = 1; i <= n; i++) out << max(res1[i], res2[i]) << ' ';
    out << '\n';
}