POJ 3298 Antimonotonicity：貪心求最長交替子序列

問題描述

給定長度 n 的序列，求最長子序列，滿足：a1 > a2 < a3 > a4 < ...（先降後升交替）。輸出最大長度。

貪心策略

從左向右掃描，只保留「峰」和「谷」。即：
- 找到第一個下降點（a[i] > a[i+1]），將 a[i] 作為第一個峰。
- 之後交替尋找谷（a[j] < a[j+1]）和峰（a[j] > a[j+1]），每找到一個長度 +1。
- 等價於：刪除所有單調段中間的元素，只保留局部極值點。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector a(n);
        for (int& x : a) cin >> x;
        if (n <= 1) { cout << n << '\n'; continue; }
        int len = 1; // 至少第一個元素
        int state = 0; // 0: 找峰(下降), 1: 找谷(上升)
        for (int i = 0; i + 1 < n; ++i) {
            if (state == 0) {
                if (a[i] > a[i+1]) { len++; state = 1; }
            } else {
                if (a[i] < a[i+1]) { len++; state = 0; }
            }
        }
        cout << len << '\n';
    }
    return 0;
}

正確性論證

• 任何合法交替子序列中，相鄰元素必為一升一降。
• 在單調遞增段中，只能取一個元素（否則會出現連續升或連續降）。取兩端點之一最優，因為它們給後續選擇留下更大空間。
• 貪心保留極值點，不會錯過更長的子序列。

複雜度

• 時間：O(n) 每測試用例。
• 空間：O(1) 額外空間（可流式處理）。

關鍵點

• 狀態機思想：交替尋找「峰」和「谷」。
• 首個元素總是算在內，後續每個極值點 +1。
• 若序列全單調，答案為 1（或 2？題目定義下全單調只能取 1 個元素，但樣例可能不同，代碼中 len 初始 1 符合「至少一個元素」）。

這題是「最長交替子序列」的貪心解法，O(n) 時間，極其高效，是序列極值點提取的典型應用。