LIS 最長遞增子序列
介紹
用下方的數列舉例
[10, 22, 33, 50, 60, 80]解釋：
10是第一個數字，作為起始點。22比10大，加入序列。9比22小，跳過。33比22大，加入序列。21比33小，跳過。50比33大，加入序列。41比50小，跳過。60比50大，加入序列。80比60大，加入序列。
最終序列為 10, 22, 33, 50, 60, 80 為什麼是這幾個數字？ 這些數字是從原數列中選出的，並且滿足以下條件：
- 遞增：每個數字都比前一個數字大。
- 最長：沒有其他遞增子序列的長度比這更長。
1. 動態規劃方法
這是LIS問題的標準解決方法。通常使用一個數組來存儲以每個元素結尾的最長遞增子序列的長度。
python
def LIS_dp(nums):
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)效率版
python
def LIS_effiently(nums):
dp = []
for num in nums:
i = 0
j = len(dp)
while i != j:
mid = (i + j) // 2
if dp[mid] < num:
i = mid + 1
else:
j = mid
if i == len(dp):
dp.append(num)
else:
dp[i] = num
return len(dp)2. (推)二分查找方法
這種方法使用二分查找來優化動態規劃解法，減少查找元素的時間覆雜度。
python
def LIS_with_bisect(nums):
from bisect import bisect_left
dp = []
for num in nums:
i = bisect_left(dp, num)
if i == len(dp):
dp.append(num)
else:
dp[i] = num
return len(dp)3. 貪心算法方法
使用貪心算法可以找到LIS的一種逼近方法。它的基本思想是盡量選擇比前一個元素大的元素，構建遞增子序列。
python
def LIS_greedy(arr):
n = len(arr)
lis = [arr[0]]
for i in range(1, n):
if arr[i] > lis[-1]:
lis.append(arr[i])
return len(lis)4. 分治法方法
分治法也可以用來解決LIS問題，將問題分解為更小的子問題。
python
def LIS_divide_conquer(arr):
def _LIS(arr, n):
if n == 1:
return 1
max_ending_here = 1
for i in range(1, n):
subproblem = _LIS(arr, i)
if arr[i - 1] < arr[n - 1] and subproblem + 1 > max_ending_here:
max_ending_here = subproblem + 1
return max(max_ending_here, _LIS(arr, n - 1))
n = len(arr)
return _LIS(arr, n)python
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print("LIS_dp:", LIS_dp(arr))
print("LIS_with_bisect:", LIS_with_bisect(arr))
print("LIS_greedy:", LIS_greedy(arr))
print("LIS_divide_conquer:", LIS_divide_conquer(arr))