題意#
這題是非常經典的演算法問題，給定一個長度為 \( n \) 的整數陣列，我們要找到它的「最長遞增子序列」（Longest Increasing Subsequence，簡稱 LIS）的長度。
也就是在不改變元素相對順序的情況下，最多能挑出多少個嚴格遞增的數字。
思路#
雖然傳統的 DP 解法空間跟時間複雜度都是 \( O(N^2) \)，但這題的 \( n \) 給到了 \( 2 \cdot 10^5 \)，平方級別的複雜度肯定會吃 TLE。因此，我們需要端出 \( O(N \log N) \) 的做法。
我們可以維護一個陣列 dp，其中 dp[k] 代表「長度為 k + 1 的遞增子序列中，結尾最小的那個數字」。
當我們依序讀取陣列元素時，如果當前數字比 dp 裡面的最後一個數字還要大，代表它可以直接接在一組最長的子序列後面，讓總長度加一。
如果沒有比較大，我們就用二分搜 (lower_bound) 找出 dp 中第一個大於或等於當前數字的元素，並把它替換掉。
這樣雖然不會增加目前的最長長度，但可以讓該長度的結尾數字變小，後續接上新數字的機會就更大了。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n; cin >> n;
vector<int> v(n), dp;
for (auto &i : v) cin >> i;
for (auto &i : v) {
// 如果 dp 是空的，或者當前數字比目前最長序列的結尾大
// 就直接接在後面，讓 LIS 長度加一
if (dp.empty() || i > dp.back()) dp.pb(i);
// 否則，找到 dp 裡面第一個 >= i 的位置，並把該位置的值替換成 i
// 這樣可以讓子序列在維持相同長度的前提下，結尾數字越小越好
else *lower_bound(all(dp), i) = i;
}
// dp 陣列的大小即為最長遞增子序列的長度
cout << dp.size() << '\n';
}
