D. Maximum Sum on Even Positions

1600
  • Quiz
  • AC
  • 解説
    • editorialと違う解法
    • 範囲の長さは偶数だけ考えればいい
    • ひっくり返した時、奇数番目と偶数番目がひっくり返るので、差し引きどれだけ得をするのか分かる
    • 隣り合うマスでペアにして、kadane's algorithmで最大部分配列を求めれば、最高の得が求まる
    • ペアの仕方は2パターンあるので両方試す

f:id:peroon:20200807044557p:plain

ll kadanes_algorithm(vector<ll> &A){
  if(SZ(A)==0) return -1;
  ll ans = A[0];
  ll s = A[0];
  FOR(i, 1, A.size()){
      s = max(s + A[i], A[i]);
      chmax(ans, s);
  }
  return ans;
}

// for codeforces
void solve(){
  ll N;
  cin>>N;
  VI A(N);
  rep(i,N)cin>>A[i];
  
  ll base = 0;
  for(int i=0; i<N; i+=2){
    base += A[i];
  }

  ll ma = base;

  // 0から
  {
    VI B;
    rep(i,N/2){
      ll a = A.at(2*i);
      ll b = A.at(2*i+1);
      B.push_back(b-a);
    }
    ll cand = base + kadanes_algorithm(B);
    chmax(ma, cand);
  }

  // 1から
  {
    ll M = N-1;
    VI B;
    rep(i,M/2){
      ll a = A.at(2*i+1);
      ll b = A.at(2*i+2);
      B.push_back(a-b);
    }
    ll cand = base + kadanes_algorithm(B);
    chmax(ma, cand);
  }
  p(ma);
}

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