最長上升子序列 II 題解
題目傳送門：AcWing 896. 最長上升子序列 II
一、題目描述
給定一個長度為 N 的數列，求數值嚴格單調遞增的子序列的長度最長是多少。
輸入格式：
- 第一行包含整數 N
- 第二行包含 N 個整數，表示完整序列
輸出格式：
- 輸出一個整數，表示最大長度
數據范圍：
- 1 ≤ N ≤ 100000
- -10? ≤ 數列中的數 ≤ 10?
二、題目分析
這道題要求我們找到一個序列中最長的嚴格遞增子序列的長度。與普通的最長上升子序列問題不同，本題的數據范圍較大（N ≤ 1e5），因此需要使用優化的算法。
三、解題思路
傳統的動態規劃解法時間復雜度為O(n2)，對于n=1e5的情況會超時。我們需要使用貪心+二分的方法將時間復雜度優化到O(nlogn)。
基本思路是維護一個數組a，其中a[i]表示長度為i+1的上升子序列的最小末尾元素。對于每個元素，我們使用二分查找來確定它應該插入的位置，從而保持數組a的單調性。
四、算法講解
算法原理
- 貪心思想：我們希望上升子序列盡可能長，因此需要讓序列上升得盡可能慢，即每次在上升子序列最后加上的數盡可能小。
- 單調性：數組a是一個嚴格遞增的數組，這保證了我們可以使用二分查找。
- 二分查找：對于每個新元素，如果它大于數組a的最后一個元素，則直接添加到末尾；否則，使用二分查找找到第一個大于等于它的位置并替換。
算法實現步驟
- 初始化空數組a和計數器cnt=0
- 遍歷輸入序列中的每個元素x：
- 如果x大于a的最后一個元素，直接添加到a末尾，cnt加1
- 否則，使用二分查找找到a中第一個大于等于x的位置，并用x替換該位置的值
- 最終cnt即為最長上升子序列的長度
例子講解
以輸入樣例為例：
7
3 1 2 1 8 5 6
處理過程：
- 3 → [3], cnt=1
- 1 → [1], cnt=1 (替換3)
- 2 → [1,2], cnt=2
- 1 → [1,2], cnt=2 (1替換1，無變化)
- 8 → [1,2,8], cnt=3
- 5 → [1,2,5], cnt=3 (替換8)
- 6 → [1,2,5,6], cnt=4
最終結果為4。
五、代碼實現
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 1e5 + 10;
int n;
int a[N];
int cnt = 0, f[N];// STL大法
void solve1()
{cin >> n;for (int i = 1; i <= n; i ++){int x;cin >> x;if (cnt == 0 || a[cnt - 1] < x)a[cnt++] = x;else*lower_bound(a, a + cnt, x) = x; // 使用STL的lower_bound找到第一個≥x的位置并替換}cout << cnt;
}// 手寫二分
void solve2()
{cin >> n;for (int i = 1; i <= n; i ++){int x;cin >> x;if (cnt == 0 || a[cnt - 1] < x)a[cnt++] = x;else{int l = -1, r = cnt + 1;while (l + 1 != r) // 二分查找第一個≥x的位置{int mid = l + r >> 1;if (a[mid] < x)l = mid;else r = mid;}a[r] = x; // 替換該位置的值}}cout << cnt;
}signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);// solve1();solve2();return 0;
}
六、重點細節
- 初始化邊界：二分查找時，左邊界設為-1，右邊界設為cnt+1，這樣可以處理所有可能的情況
- 嚴格遞增：題目要求嚴格遞增，因此比較時使用<而不是≤
- 替換策略：當找到第一個≥x的位置時，直接替換可以保證后續更長的子序列更容易形成
- 數組維護：數組a的長度cnt即為當前找到的最長上升子序列長度
七、復雜度分析
- 時間復雜度：O(nlogn)，每個元素需要進行一次二分查找，二分查找的時間復雜度為O(logn)
- 空間復雜度：O(n)，需要額外的數組a來存儲中間結果
八、總結
本題通過貪心+二分的方法，將最長上升子序列問題的時間復雜度從O(n2)優化到O(nlogn)，能夠高效處理大規模數據。關鍵在于維護一個單調遞增的數組，并通過二分查找來快速確定每個元素的插入位置。
)
)
