CF2064C: Remove the Ends

Problem — C — Codeforces 2064C - Remove the Ends

Approach 1 (TLE): Memoized Search

Direct memoized search using unordered_map. We need to combine l and r states into a single long long for storage. Unfortunately, TLEs on test case 5.

// Note: TLE
#include <bits/stdc++.h>
using namespace std;
static inline long long encodeState(int l, int r) {
    return ((long long)l << 32) | (unsigned int)r;
}

unordered_map<long long, long long> dpMemo;

vector<int> a;

long long dp(int l, int r) {
    if (l > r)
        return 0;
    long long key = encodeState(l, r);
    if (dpMemo.count(key))
        return dpMemo[key];
    long long best = -LLONG_MAX / 2;
    for (int i = l; i <= r; i++) {
        if (a[i] > 0) {
            best = max(best, (long long)a[i] + dp(i + 1, r));
        } else if (a[i] < 0) {
            best = max(best, (long long)(-a[i]) + dp(l, i - 1));
        }
    }
    dpMemo[key] = best;
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        a.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        dpMemo.clear();
        long long ans = dp(1, n);
        cout << ans << "\n";
    }
    return 0;
}

Approach 2 (AC): Left-Right DP Merge

Let's look for patterns: - If array a is all positive, maximize by taking left to right: $$$ans=\sum^n_{i=0}a_i$$$ - If all negative, take right to left - Or split: take [0,i] from left and [i+1,n] from right

We can use two DP arrays: p_dp (prefix) and s_dp (suffix). $$$p_dp[i]$$$ represents maximum answer taking positives from left up to position i:

Important constraints:

The third way combines prefix and suffix:

Final answer is maximum of all three approaches:

Code:

/*
 * Created by: Chixiyu
 * Date: 2025-02-17
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll NEG_INF = -1000000000000000000LL; // -1e18

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // prefix
    vector<ll> prefix_dp(n + 1, NEG_INF);
    ll prefix_ans;
    ll prev_max = 0; // prevmax= max(a[0,i-1])
    prefix_dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > 0) { // can prefix dp1
            prefix_dp[i] = max(prefix_dp[i], a[i] + prev_max);
            // update prev_max
            prev_max = max(prev_max, prefix_dp[i]);
        }
    }
    prefix_ans = prefix_dp[n];
    // suffix
    vector<ll> suffix_dp(n + 1, NEG_INF);
    ll suffix_ans;
    prev_max = 0;
    // inverse the array
    reverse(++a.begin(), a.end());
    suffix_dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] < 0) { // can suffix dp
            suffix_dp[i] = max(suffix_dp[i], -a[i] + prev_max);
            prev_max = max(prev_max, suffix_dp[i]);
        }
    }
    suffix_ans = suffix_dp[n];
    // calculate combined
    ll combined_ans = NEG_INF;
    for (int i = 0; i <= n; i++) {
        ll left = prefix_dp[i];
        ll right = 0;
        if (i != n) {
            right = suffix_dp[n - i];
        }
        combined_ans = max(combined_ans, left + right);
    }
    cout << max({prefix_ans, suffix_ans, combined_ans}) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}