Lis算法輸出最長子序列

LIS（Longest Increasing Subsequence）算法用於找出一個序列中的最長上升子序列。所謂上升子序列，是指一個子序列，其元素是嚴格遞增的。例如，對於序列[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13]，其最長上升子序列為[2, 6, 9, 13]，因為它是所有上升子序列中最長的。

LIS算法可以通過動態規劃來解決。我們定義lis[i]為以a[i]為最後一個元素的最長上升子序列的長度。我們可以通過如下的方法來計算lis[i]：

1. 對於每個i，我們可以將a[i]加到以a[0..i-1]中任何一個元素結尾的LIS上。
2. 因此，lis[i]等於lis[0..i-1]中的最大元素加上1，如果a[i]大於這些LIS的最後一個元素，否則為1。

我們可以通過掃描整個數組來計算lis[0..n-1]，然後找出lis[0..n-1]中的最大元素，這個最大元素就是整個序列的最長上升子序列的長度。

以下是一個簡單的Python實現：

def lis(a):
    n = len(a)
    lis = [1] * n  # 初始化每個元素的LIS長度為1
    for i in range(n):
        for j in range(i):
            if a[i] > a[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
    return max(lis)

# 示例
a = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13]
print(lis(a))  # 輸出：4

這個算法的時間複雜度為O(n^2)，因為我們需要遍歷整個數組兩次。對於某些特定的輸入，存線上性時間複雜度的LIS算法，但通常情況下，這個簡單的算法就足夠了。