これまたちょっと重たい。。。

問題概要

折れ線グラフが与えられる。これは $i = 1, 2, \dots, N$ に対して

( $i, A_i$ )

を結んでいる。あらゆる水平な直線を考えたときの、折れ線グラフのうち直線の上に来ている部分を連結成分ごとに分解したとき、連結成分の個数として考えられる最大値を求めよ。

考えたこと

直感的に、

山頂 (のちょっと下)
谷底 (のちょっと上)

だけを考えればいいことがわかる。これにより候補は高々 $N$ 通りに限られる。

各候補についての処理に $O(N)$ かけられないので高速に更新しなければならない。そこで、最も標高の高い山頂からスタートして、少しずつ下っていけばいい。上から順に、山頂または谷底を走査して、その時点での連結成分の個数は

山頂だったら、+1
谷底だったら、-1

という風にしていけばいい。実装はちょっとめんどい。。。

注意点として、A[ i ] = A[ i + 1 ] みたいなところがあると山頂だか谷底だか峠だかわからないので、こういうのは最初に圧縮しておくことにした。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pint = pair<int, int>;

int main() {
    int N; cin >> N;
    vector<pint> B;
    vector<int> A;
    
    // A[i] = A[i+1] みたいなところは 1 つの点に圧縮する
    int prev = -1;
    for (int i = 0; i < N; ++i) {
        int a; cin >> a;
        if (a != prev) {
            B.push_back(pint(a, B.size())); // B は index も付け加える
            A.push_back(a);
            prev = a;
        }
    }
    sort(B.begin(), B.end(), greater<pint>());
    
    // 折れ線の折れ曲がりがない場合は例外
    if (A.size() == 1) {
        if (A[0] > 0) cout << 1 << endl;
        else cout << 0 << endl;
    }
    else {
        // 上から順番に走査していく
        int res = 1;
        int cur = 0;
        for (int i = 0; i < B.size(); ++i) {
            int id = B[i].second;
            
            if (id == 0) {
                if (A[id] > A[id+1]) ++cur;
            }
            else if (id == A.size() - 1) {
                if (A[id-1] < A[id]) ++cur;
            }
            else {
                if (A[id-1] < A[id] && A[id] > A[id+1]) ++cur;
                else if (A[id-1] > A[id] && A[id] < A[id+1]) --cur;
            }

            // 同一高さに複数の「山頂」や「谷底」がある場合は、その高さの処理をすべて終えてから更新する
            if (i == (int)B.size() - 1 || B[i].first != B[i+1].first) {
                res = max(res, cur);
                prev = B[i].first;
            }
        }
        cout << res << endl;
    }
}