公式

A - 連続上昇気温 / Consecutive Rising Temperatures 解説 by physics0523


初心者の方へ


隣接項 \(A_k,A_{k+1}\) について \(A_k<A_{k+1}\) となることが最も長く連続する部分を検出すればよいです。
このためには、 \(A_k<A_{k+1}\) となる部分を繋げられるだけ繋げ、 \(A_k \ge A_{k+1}\) となるなら直ちに分断するとよいです。

以下の手続きで正解できます。

  • 現在の上昇期間 \(cur=1\) 、答え \(res=1\) と初期化します。
  • \(i=2,3,\dots,N\) について、以下を繰り返す。
    • \(A_{i-1} < A_i\) なら現在の上昇期間が続くため、 \(cur\)\(1\) 加算する。
    • \(A_{i-1} \ge A_i\) ならこれ以上上昇期間を延ばすことができず新たな上昇期間が始まるため、 \(cur=1\) とする。
    • \(res=\max(res,cur)\) とする。

メモ: \(-40 \le A_i \le 45\) より上昇期間の最大の長さは高々 \(86\) です。このことから、より愚直な解法でも正答できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(auto &nx : A){cin >> nx;}
  int res=1,cur=1;
  for(int i=1;i<N;i++){
    if(A[i-1]<A[i]){
      cur++;
    }
    else{
      cur=1;
    }
    res=max(res,cur);
  }
  cout << res << "\n";
  return 0;
}

投稿日時:
最終更新: