C. Alternating Subsequence ～正負で分割～

• Quiz
  • https://codeforces.com/problemset/problem/1343/C
• AC
  • https://codeforces.com/contest/1343/submission/87007538
• 解法
  • 配列を正負で分割してそれぞれでMaxをとる

code

// 正負で分割
// 例 1 2 3 -1 -2 => {1,2,3},{-1,-2}
VV f(VI& A){
  ll N = A.size();
  ll cross = 0;
  rep(i,N-1){
    if(A[i]*A[i+1]<0)cross++;
  }
  ll M = cross+1;
  VV G(M);
  bool plus;
  if(A[0]>0){
    plus=true;
  }else{
    plus=false;
  }
  ll idx=0;
  rep(i,N){
    ll a = A[i];
    if(plus && a<0){
      idx++;
      plus = !plus;
    }
    else if(!plus && a>0){
      idx++;
      plus = !plus;
    }
    G[idx].push_back(a);
  }
  return G;
}

// for codeforces
void solve(){
  ll N;cin>>N;
  VI A(N);
  rep(i, N) cin >> A[i];
  auto G = f(A);
  ll sum=0;
  for(VI A : G){
    sum += MAX(A);
  }
  p(sum);
}

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

    // input
    ll N; 
    cin>>N;
    
    while(N--)solve();
    
    return 0;
}