BOJ 22970 - 문제 재탕

image.png

어떤 $i$를 기준으로 좌우로 얼마나 이어지는지 세면 된다.

이 방법은 $O(n^2)$ 일 것 같지만 실제론 $O(n)$이다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   int ans = 1;

   for (int i = 0; i < n; i++) {
      int j = i;
      while (j + 1 < n && a[j] < a[j + 1])j++;
      int k = j;
      while (k + 1 < n && a[k] > a[k + 1])k++;
      maxa(ans, k - i + 1);
      i = j;
   }
   cout << ans;
}

Tags:

Categories:

Updated:

Comments