一本通-1283：登山（LIS的合唱队形）

【题目描述】 五一到了，ACM队组织大家去登山观光，队员们发现山上一个有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

【输入】 第一行：N (2 ≤ N ≤ 1000) 景点数;

第二行：N个整数，每个景点的海拔。

【输出】 最多能浏览的景点数。

【输入样例】 8 186 186 150 200 160 130 197 220

【输出样例】 4

---

题意是必须保证严格单增或单减（因为不浏览海拔相同的高度），到某一高度开始下山，意味着下山也可以浏览其他经典，于是就变成了合唱队形的模型，也就是先找最长上升子序列，再找下降的序列，然后让整个序列的长度最长。

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> seq(1005);
vector<int> d(1005), c(1005), forwardSeq(1005), backwardSeq(1005);

int solve()
{
    forwardSeq[1] = seq[0];
    d[1] = 1;
    int len1 = 1;
    for (int i = 1; i < n; ++i) {
        int target = seq[i];

        int left = 1, right = len1 + 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (forwardSeq[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (left == len1 + 1) {
            forwardSeq[++len1] = target;
            d[i + 1] = len1; 
        }
        else {
            forwardSeq[left] = target;
            d[i + 1] = left;
        }
    }

    backwardSeq[1] = seq[n - 1];
    c[n] = 1;
    int len2 = 1;
    for (int i = n - 2; i >= 0; --i) {
        int target = seq[i];

        int left = 1, right = len2 + 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (backwardSeq[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (left == len2 + 1) {
            backwardSeq[++len2] = target;
            c[i + 1] = len2; 
        }
        else {
            backwardSeq[left] = target;
            c[i + 1] = left;
        }
    }

    int maxVal = 0;
    for (int i = 1; i <= n; ++i) {
        maxVal = max(maxVal, d[i] + c[i] - 1);
    }

    return maxVal;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> seq[i];

    cout << solve() << endl;

    return 0;
}