BOJ 22970 - 문제 재탕
어떤 $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;
}
Comments