山登り・登山の最大負荷

• 自分検索用に上記タイトルにした

code

// 山登りの最大負荷
// A[i] = -1 or 0 or 1
// 最大上昇を返す
ll max_fatigue(VI& A){
  ll ma=0;
  ll cur=0;
  ll N = A.size();
  rep(i,N){
    cur += A[i];
    chmax(ma, cur);
    if(cur<0) cur=0;
  }
  return ma;
}

what is this?

• 左から右に山登りしているとして、いつが1番キツイだろうか？
• 登る時キツイとする
• ある範囲を切り取った時に1番上昇量が多ければキツイとし、それを返す（画像の６）

verified

• E - Binary Subsequence Rotation
  • https://codeforces.com/contest/1370/submission/85826458

This is ...

• Yes, kadane's algorithm