NY OJ 17：最長遞增子序列長度 (O(n²) DP)

問題描述

給定 n (≤20) 個字符串，每串長度 ≤10000。求每個字符串的最長嚴格遞增子序列（按字符 ASCII 碼比較）長度。輸入字符串可能包含任意可見字符。

標準 DP 解法

dp[i] 以第 i 個字符結尾的 LIS 長度。轉移：

dp[i] = 1 + max{ dp[j] | j < i, s[j] < s[i] }

答案為 max dp[i]。時間 O(L²)，L ≤ 10000 → 10⁸ 操作，單測試案例邊界緊湊但通常可過（C++ 優化後）。

優化：O(L log L) 貪心 + 二分

維護數組 tails[len] 表示長度為 len 的遞增子序列的最小結尾值。遍歷字符 c：

• 二分查找 tails 中第一個 ≥ c 的位置 pos。
• tails[pos] = c；若 pos 超出當前長度，長度加一。

最終長度即答案。時間 O(L log L)，極其穩健。

參考代碼 (C++ O(L log L))

#include 
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    string s;
    while (T--) {
        cin >> s;
        vector tails;
        for (char c : s) {
            auto it = lower_bound(tails.begin(), tails.end(), c);
            if (it == tails.end()) tails.push_back(c);
            else *it = c;
        }
        cout << tails.size() << '\n';
    }
    return 0;
}

關鍵點

• lower_bound 實現「嚴格遞增」：找第一個 ≥ c，替換之；若要「非嚴格遞增」用 upper_bound。
• tails 始終嚴格遞增，二分合法。
• 字符串長度 10000，O(L²) 可能 TLE，O(L log L) 必須掌握。

總結

• LIS 經典問題，O(n log n) 算法是必考內容。
• 字符串視為字符序列，直接應用通用 LIS 模板。
• 多測試案例獨立處理，清空 tails。