Lower [AtCoder Beginner Contest 139 C]

https://atcoder.jp/contests/abc139/tasks/abc139_c

解説

https://atcoder.jp/contests/abc139/submissions/7338829

全探索を考える。
始点を全探索して、右側にどれだけ移動できるかを確かめると、O(N²)で解が求まる。
例えば、「6 5 4 9」
となっていて、6を始点とすると、6 5 4が最長であると分かる。
この時、5を始点としたチェックは6 5 4に含まれ、最適ではないので、チェックする必要はない。
つまり、始点を全探索するが、チェック済みの部分については、再度チェックしなくていい。

int N, H[101010];
bool checked[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> H[i];

    int ans = 0;
    rep(i, 0, N) if(!checked[i]) {
        checked[i] = true;
        rep(j, i + 1, N) {
            if(H[j - 1] < H[j])
                break;
            checked[j] = true;
            chmax(ans, j - i);
        }
    }
    cout << ans << endl;
}