UVA 10534 Wavio Sequence：O(n log n) LIS 求最長波谷子序列

• 遍歷 a[i]，在 g 中二分查找第一個 ≥ a[i] 的位置 pos
• dp[i] = pos，更新 g[pos] = a[i]
• g 單調遞增，保證二分正確

雙向計算

1. 正向跑 LIS 得 dp1[i] = 以 i 結尾的最長遞增子序列長度
2. 反向跑 LIS 得 dp2[i] = 以 i 開頭的最長遞減子序列長度（相當於反序列的 LIS）

完整代碼

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 10010;
const int INF = 1 << 30;

int n, a[MAXN], dp1[MAXN], dp2[MAXN], g[MAXN];

void LIS_forward() {
    for (int i = 1; i <= n; ++i) g[i] = INF;
    for (int i = 1; i <= n; ++i) {
        int k = lower_bound(g + 1, g + n + 1, a[i]) - g;
        dp1[i] = k;
        g[k] = a[i];
    }
}

void LIS_backward() {
    for (int i = 1; i <= n; ++i) g[i] = INF;
    for (int i = n; i >= 1; --i) {
        int k = lower_bound(g + 1, g + n + 1, a[i]) - g;
        dp2[i] = k;
        g[k] = a[i];
    }
}

int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        LIS_forward();
        LIS_backward();
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            ans = max(ans, 2 * min(dp1[i], dp2[i]) - 1);
        printf("%d\n", ans);
    }
    return 0;
}

關鍵點總結

複雜度

• 時間：O(n log n) × 2 = O(n log n)
• 空間：O(n)

此題是 LIS 經典變體，雙向 O(n log n) LIS 模板必背。注意 lower_bound 用於非嚴格遞增，本題要求嚴格遞增，因 g 維護最小結尾值，相等時替換不影響長度計算，故正確。