lis 簡例

 a = [10,20,30,5,15,25]

n = len(a)
lis_lengths = [1]*n

for i in range(1,n):
    for j in range(0,i):
        if a[i]>a[j] and lis_lengths[j]<lis_lengths[j]+1:
            lis_lengths[i] = lis_lengths[j]+1
print(max(lis_lengths))

程式碼說明

這段程式的目的是找出陣列 a 中的最長遞增子序列（LIS）的長度。它使用了一個動態規劃的方法，用 lis_lengths 陣列來記錄從每個元素開始的最長遞增子序列的長度。

初始變數

• a = [10, 20, 30, 5, 15, 25]
• n = len(a) = 6
• lis_lengths = [1, 1, 1, 1, 1, 1]：初始值為 1，因為每個元素本身就可以視為長度為 1 的遞增序列。

執行過程

程式使用雙重迴圈，依序比較每個元素與它之前的所有元素。若元素間能形成遞增序列且新的長度比之前記錄的長度長，則更新 lis_lengths 陣列中的值。以下是每個步驟的更新結果：

1. i = 1

   • a[1] = 20 和 a[0] = 10 可以形成遞增序列。
   • 更新 lis_lengths[1] 為 2。
   • lis_lengths 變為 [1, 2, 1, 1, 1, 1]

2. i = 2

   • a[2] = 30 分別與 a[0] = 10 和 a[1] = 20 可以形成遞增序列。
   • 更新 lis_lengths[2] 最終為 3。
   • lis_lengths 變為 [1, 2, 3, 1, 1, 1]

3. i = 3

   • a[3] = 5 沒有與前面的元素形成遞增序列。
   • lis_lengths 保持不變 [1, 2, 3, 1, 1, 1]

4. i = 4

   • a[4] = 15 與 a[0] = 10 可以形成遞增序列。
   • 更新 lis_lengths[4] 為 2。
   • lis_lengths 變為 [1, 2, 3, 1, 2, 1]

5. i = 5

   • a[5] = 25 與 a[0] = 10 和 a[1] = 20 形成遞增序列，最終更新 lis_lengths[5] 為 3。
   • lis_lengths 變為 [1, 2, 3, 1, 2, 3]

最終結果

• 最後 lis_lengths 陣列中的最大值即為最長遞增子序列的長度，max(lis_lengths) = 3。

• 因此，陣列 a = [10, 20, 30, 5, 15, 25] 中的最長遞增子序列長度為 3。