山のデータ
問題
B – 山のデータ
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…
解法
- どれだけ増え続けているかとどれだけ減り続けているかを別に管理して数える(累積和風)。
- 減り続けている方は後ろから見る。
- 各点のそれぞれの値 \(+1\)
コード例
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using P = pair<int, int>; #define rep(i, n) for(int i = 0; i < (n); ++i) // using mint = modint998244353; // using mint = modint1000000007; // const int mod = 1000000007; // const ll INF = 1LL << 60; // const int INF = 1001001001; // ARC036-B // https://atcoder.jp/contests/arc036/tasks/arc036_b /** * 6 4 5 1 6 9 7 */ int main() { int N; cin >> N; vector<int> h(N); rep(i, N) { cin >> h[i]; } vector<int> l(N); rep(i, N - 1) { if(h[i] < h[i + 1]) { l[i + 1] = l[i] + 1; } else { l[i + 1] = 0; } } vector<int> r(N); for(int i = N - 2; 0 <= i; --i) { if(h[i + 1] < h[i]) { r[i] = r[i + 1] + 1; } else { r[i] = 0; } } int ans = 0; rep(i, N) { ans = max(ans, l[i] + r[i] + 1); } cout << ans << endl; return 0; }