ABC139 C - Lower

備忘録

問題

atcoder.jp

回答

"use strict"
 
function Main(input) {
  input = input.trim().split('\n');
  const N = Number(input[0]);
  const H = input[1].trim().split(' ').map(Number);
 
  let ret = 0;
  let move = 0;
  
  for(let i=0; i<N; i++){
    if (H[i] >= H[i+1]) {
      move += 1;
    } else {
      ret = Math.max(ret, move);
      move = 0;
    }
  }
 
  console.log(ret);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

考え方

自身のマスと隣のマスを比較し、隣のマスが自身の高さ以下の場合、移動可能としてmoveを+1する。
自身のマスと隣のマスを比較し、隣のマスが自身の高さ以上の場合、移動不可としてmoveを初期化(0)する。
（この時、移動可能だったマス数の最大値を保持しておく）

基本的にはforで自身と一つ先のマスの高さを比較し、移動できたマス数を保持しておくだけで回答できる。
forを2重ループにして回答することも可能だと思うが、
その場合はNが最大1e5のため、O(N^10)になるのでLTEになる（と思う）