JOI2019/2020 一次予選第三回 C問題解説

問題

問題文

長さNの正整数列A=(A1,A2,…,AN)が与えられる．正整数列Aの連続部分列の中で昇順に並んでいるもののうち，最長のものの長さを求めよ． すなわち，Al≦Al+1≦⋯≦Ar 満たすような2つの整数l,r (1≦l≦r≦N)について，r−l+1 の最大値を求めよ．

制約

1≦N≦100
1≦Ai≦2020 (1≦i≦N)

入力

N
A1 A2⋯AN

※問題文、制約、入力の情報は日本情報オリンピック委員会に帰属し、CC4.0 BY-SAで提供されています。 また本記事はCC4.0 BY-SAを継承しています

解説

数列が与えられるからこのときforループで入力を取る。（以下for(int i=0;i<N;i++){}のループを指す）

このときに判断するとコードが短くて済む。

出力される数字は1以上だということに注意。

変数

int S,N,cnt,ans;

cntとansはそれぞれ1で初期化している。

• if文でiが0でないこと、かつi-1はiよりも小さいかについて評価する。
  • 上が真のとき、cnt(現時点で数字が続いている数)に+1する
    • ans <= cntのときcnt に ans を代入
  • cnt に 1を代入する。

問題文より、連続する数がない場合でも1個連続しているとなるから答えは1以上である。

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

int main(){
    int N,A[100];
    cin >> N;
    int ans=1,cnt=1;
    for(int i=0;i<N;i++){
        cin >> A[i];
        if(i != 0 && A[i-1] <= A[i]){
            cnt ++;
            if(ans <= cnt){
                ans = cnt;
            }
        }else{
            cnt = 1;
        }
    }
    cout << ans;
}