Uva10534 - Wavio Sequence

題目大意

給一個序列，要我們找出前 (n-1) 是升序後面 (n-1)降序的最長子序列長度

重點觀念

• LIS 參考 http://web.ntnu.edu.tw/~algo/Subsequence.html

分析

• 正反各做一次 LIS 記錄個 index 的 position
• 最後再遍歷一遍找最大的 n*2+1 即是答案

程式題目碼

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        int a[n];
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        int lis[n];  // 紀錄左到右的 lis 位置
        int lds[n];  // 紀錄左道揍的 lds 位置

        vector<int> dp;
        dp.push_back(a[0]);
        for (int i = 0; i < n; i++) {
            if (a[i] > dp.back()) {
                lis[i] = dp.size();
                dp.push_back(a[i]);

            } else {
                dp[lis[i] = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin()] = a[i];
            }
        }
        dp.resize(0);
        dp.push_back(a[n - 1]);
        for (int i = n - 1; i >= 0; i--) {
            if (a[i] > dp.back()) {
                lds[i] = dp.size();
                dp.push_back(a[i]);
            } else {
                lds[i] = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();
                dp[lds[i]] = a[i];
            }
        }

        int ans = 0;

        for (int i = 0; i < n; i++) {
            ans = max(ans, min(lis[i], lds[i]) * 2 + 1);
        }

        cout << ans << endl;
    }

    return 0;
}