Codeforces Round 1005 (Div. 2) C

题目描述

点击跳转原题

思路

dp[0]记录当前连续正数的绝对值和。
dp[1]记录包含当前处理过元素后最大值，可能包含正数和某些负数的绝对值。
维护两种状态，选择更优路径。

代码

#define akitama return 0
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define fast_io cin.tie(nullptr)->ios::sync_with_stdio(false)
#define endl '\n'

void solve() {
    int n; cin >> n;

    vl dp(2);
    for(int i = 0;i < n; ++ i) {
        ll t;
        cin >> t;
        if(t < 0) dp[1] -= t;
        else dp[0] += t;

        if(dp[1] < dp[0]) {
            dp[1] = dp[0];
        }
    }

    cout << dp[1] << endl;
}

signed main(){
    fast_io;
    int _ ;
    cin >> _;
    while (_--) {
        solve();
    }
    akitama;
}