經典算法——最長遞增子序列

最長遞增子序列（Longest Increasing Subsequence, LIS）

一、概念與問題描述

最長遞增子序列是一個在給定的未排序數組中找到最長的非降序子序列，其中每個元素嚴格大於其前一個元素。例如，在序列 [10, 9, 2, 5, 3, 7, 101, 18] 中，最長遞增子序列為 [2, 3, 7, 101]。

二、解決方法與動態規劃

使用動態規劃來解決最長遞增子序列問題：

1. 定義狀態：

假設 dp[i] 表示以數組中的第 i 個元素結尾的最長遞增子序列的長度。

2. 狀態轉移方程：

對於數組中的每一個元素 arr[i]，我們有兩種選擇：

• 如果 arr[i] 能夠加入到之前某個比它小的元素後構成新的遞增子序列，則 dp[i] = dp[j] 1，其中 j 是滿足 arr[j] < arr[i] 並且 dp[j] 最大的索引。

• 否則，如果沒有任何比 arr[i] 小的元素適合加入遞增子序列，則 dp[i] = 1。

3. 初始化：

所有 dp[i] 初始化為1，表示最短遞增子序列至少包含一個元素。

4. 計算結果：

長度最大的 dp[i] 即為整個數組的最長遞增子序列長度。

C 示例代碼片段

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 計算給定數組的最長遞增子序列長度
int longestIncreasingSubsequence(vector<int>& nums) {
	int n = nums.size();
	vector<int> dp(n, 1); // 初始化dp數組
	for (int i = 1; i < n;   i) {
		for (int j = 0; j < i;   j) {
			if (nums[i] > nums[j]) { // 當nums[i]大於nums[j]
				dp[i] = max(dp[i], dp[j]   1); // 更新dp[i]為當前最大值和dp[j] 1的最大值
			}
		}
	}
	return *max_element(dp.begin(), dp.end()); // 返回dp數組中的最大值
}
int main() {
	vector<int> nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
	cout << "Length of the Longest Increasing Subsequence: "
		<< longestIncreasingSubsequence(nums) << endl;
	return 0;
}

這段代碼首先初始化了一個大小與輸入數組相同的 dp 數組，並通過兩層循環比較數組中的每對元素，更新 dp 數組。最後返回 dp 數組中的最大值，即為原數組的最長遞增子序列長度。

註意，上述代碼僅計算了最長遞增子序列的長度，若要獲取具體的最長遞增子序列，還需要額外記錄下構造該序列的過程。