[Codeforces Round 1005(Div. 2)] - C. Remove the ends

https://codeforces.com/contest/2064/problem/C

Codeforces Round 1005(Div. 2) - C. Remove the ends

문제 유형: 그리디, 해 구성하기, 모노토닉, 구간합, 브루트 포스

시간 제한: 3초

메모리 제한: 256MB

 

문제

You have an array a of length n consisting of non-zero integers. Initially, you have 0 coins, and you will do the following until a is empty:

• Let m be the current size of a. Select an integer i where 1≤i≤m, gain |ai|∗ coins, and then:

• if ai<0, then replace a with [a1,a2,…,ai−1] (that is, delete the suffix beginning with ai);
• otherwise, replace awith [ai+1,ai+2,…,am] (that is, delete the prefix ending with ai).

 

Find the maximum number of coins you can have at the end of the process.

 

n의길이의 정수배열 a가 주어진다. 내부의 값에는 0이 없다. 처음에는 0개의 코인을 가진다.

다음의 작업을 a가 빌 때까지 할 것이다:

m을 남은 배열의 길이라 할때, 1 <= i <= m을 골라서, |a_i|만큼의 코인을 얻는다.

a_i가 음수이면, 배열의 구간을 [a1, a2, ... ai-1]로 줄인다.

a_i가 양수이면, 배열의 구간을 [ai+1, ..., am]으로 줄인다.

 

최종적으로 얻을 수 있는 코인의 최대값을 구하시오.

 

입력

The first line contains an integer t (1≤t≤10^4) — the number of testcases.

The first line of each testcase contains an integer n (1≤n≤2⋅10^5) — the length of a.

The second line of each testcase contains n integers a1,a2,…,an (−10^9≤ai≤10^9, ai≠0).

The sum of n across all testcases does not exceed 2⋅10^5.

 

첫째 줄에 테스트케이스의 수 t가 주어진다.

각 테스트케이스의 첫 줄에는 배열의 길이 n이 주어진다.

둘째 줄에는 배열 a의 요소들이 주어진다.

 

출력

For each test case, output the maximum number of coins you can have at the end of the process.

 

각 테스트케이스별로 얻을 수 있는 최대 코인을 출력하시오.

 

풀이

그리디하게 생각했을 때, 맨 왼쪽에 붙은 양수부터, 그리고 맨 오른쪽에 붙은 음수부터 제거할수록 배열의 손실을 최소화하면서 코인을 얻을 수 있다는 것을 알 수 있다.

 

pref[i]를 0~i까지의 양수들의 합, suff[i]를 i~n까지의 음수들의 절대값 합이라 하자.

얻을 수 있는 동전의 최대값은 max(pref[i] + suff[i]) for i := 0 ... n이다.

 

 

코드

C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<ll> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  vector<ll> pref(n), suff(n);

  if (a[0] > 0)
    pref[0] = a[0];
  for (int i = 1; i < n; ++i) {
    pref[i] = pref[i - 1];
    if (a[i] > 0) {
      pref[i] += a[i];
    }
  }

  if (a[n - 1] < 0) {
    suff[n - 1] = -a[n - 1];
  }
  for (int i = n - 2; i >= 0; --i) {
    suff[i] = suff[i + 1];
    if (a[i] < 0) {
      suff[i] -= a[i];
    }
  }

  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    ans = max(ans, pref[i] + suff[i]);
  }

  cout << ans << "\n";
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}