列出最長遞增子序列（LIS）

 要在程式中列出實際的最長遞增子序列（LIS），可以在計算每個位置的 LIS 長度時，記錄下最長子序列的路徑。

# 輸入的陣列
a = [10, 20, 30, 5, 15, 25]
n = len(a)

# 初始化每個位置的最長遞增子序列長度為1
lis_lengths = [1] * n

# 初始化每個位置的前驅索引，用來追蹤最長子序列的路徑
previous_index = [-1] * n

# 計算每個位置的最長遞增子序列長度並記錄路徑
for i in range(1, n):
    for j in range(0, i):
        if a[i] > a[j] and lis_lengths[i] < lis_lengths[j] + 1:
            lis_lengths[i] = lis_lengths[j] + 1
            previous_index[i] = j  # 記錄位置 j 作為 i 的前驅

# 找出最長遞增子序列的長度及其結尾索引
max_length = max(lis_lengths)
max_index = lis_lengths.index(max_length)

# 追蹤回去找到最長遞增子序列
lis_sequence = []
while max_index != -1:
    lis_sequence.append(a[max_index])
    max_index = previous_index[max_index]

# 由於是從後往前追蹤，所以需要反轉序列
lis_sequence.reverse()

# 輸出結果
print("最長遞增子序列的長度是:", max_length)
print("最長遞增子序列為:", lis_sequence)

程式碼說明

1. 變數初始化：

   • lis_lengths：用來儲存以每個位置為結尾的最長遞增子序列長度，初始值設為 1。
   • previous_index：用來記錄每個元素在 LIS 中的前驅索引，初始值設為 -1。

2. 計算最長遞增子序列長度和前驅索引：

   • 使用兩層迴圈更新 lis_lengths 和 previous_index。
   • 當 a[i] > a[j] 且可以延長 LIS 時，更新 lis_lengths[i] 並將 previous_index[i] 設為 j，表示 a[j] 是 a[i] 的前驅。

3. 找到最長 LIS：

   • 使用 max(lis_lengths) 找到 LIS 的長度，並用 lis_lengths.index(max_length) 找到 LIS 的結尾索引 max_index。

4. 回溯找出 LIS：

   • 使用 previous_index 從 max_index 回溯，逐步找到 LIS 中的元素，並存入 lis_sequence。
   • 回溯結束後，反轉 lis_sequence 得到正確順序的 LIS。

執行結果

如果使用範例陣列 a = [10, 20, 30, 5, 15, 25]，執行結果會是：

最長遞增子序列的長度是: 3
最長遞增子序列為: [10, 20, 30] 或 [5, 15, 25]（取決於程式的路徑選擇）

這樣的程式碼可以輸出 LIS 的長度以及實際的最長遞增子序列。

好的，讓我們逐步追踪這段程式碼的執行過程，看看如何找到最長遞增子序列。

初始變數

1. 輸入陣列：a = [10, 20, 30, 5, 15, 25]
2. 長度：n = 6
3. 最長遞增子序列長度陣列：lis_lengths = [1, 1, 1, 1, 1, 1]，每個元素都初始化為 1，表示每個元素本身都是一個長度為 1 的子序列。
4. 前驅索引陣列：previous_index = [-1, -1, -1, -1, -1, -1]，初始化為 -1，表示每個元素的前驅尚未確定。

追踪過程

我們會對每一對元素 (a[j], a[i]) 進行比較，並根據條件更新 lis_lengths 和 previous_index。

1. i = 1

   • a[1] = 20
   • 比較 a[0] < a[1] (10 < 20)，條件成立。
   • 更新 lis_lengths[1] = lis_lengths[0] + 1 = 2
   • 更新 previous_index[1] = 0，表示 a[0] 是 a[1] 的前驅。
   • 狀態更新：
     • lis_lengths = [1, 2, 1, 1, 1, 1]
     • previous_index = [-1, 0, -1, -1, -1, -1]

2. i = 2

   • a[2] = 30
   • 比較 a[0] < a[2] (10 < 30)，條件成立。
   • 更新 lis_lengths[2] = lis_lengths[0] + 1 = 2
   • 更新 previous_index[2] = 0，表示 a[0] 是 a[2] 的前驅。
   • 比較 a[1] < a[2] (20 < 30)，條件成立。
   • 更新 lis_lengths[2] = lis_lengths[1] + 1 = 3
   • 更新 previous_index[2] = 1，表示 a[1] 是 a[2] 的前驅。
   • 狀態更新：
     • lis_lengths = [1, 2, 3, 1, 1, 1]
     • previous_index = [-1, 0, 1, -1, -1, -1]

3. i = 3

   • a[3] = 5
   • 比較 a[0] < a[3] (10 < 5)，條件不成立。
   • 比較 a[1] < a[3] (20 < 5)，條件不成立。
   • 比較 a[2] < a[3] (30 < 5)，條件不成立。
   • 狀態保持不變：
     • lis_lengths = [1, 2, 3, 1, 1, 1]
     • previous_index = [-1, 0, 1, -1, -1, -1]

4. i = 4

   • a[4] = 15
   • 比較 a[0] < a[4] (10 < 15)，條件成立。
   • 更新 lis_lengths[4] = lis_lengths[0] + 1 = 2
   • 更新 previous_index[4] = 0，表示 a[0] 是 a[4] 的前驅。
   • 比較 a[1] < a[4] (20 < 15)，條件不成立。
   • 比較 a[2] < a[4] (30 < 15)，條件不成立。
   • 比較 a[3] < a[4] (5 < 15)，條件成立。
   • 更新 lis_lengths[4] = lis_lengths[3] + 1 = 2（與 lis_lengths[4] 相等，因此保持不變）
   • 狀態更新：
     • lis_lengths = [1, 2, 3, 1, 2, 1]
     • previous_index = [-1, 0, 1, -1, 0, -1]

5. i = 5

   • a[5] = 25
   • 比較 a[0] < a[5] (10 < 25)，條件成立。
   • 更新 lis_lengths[5] = lis_lengths[0] + 1 = 2
   • 更新 previous_index[5] = 0，表示 a[0] 是 a[5] 的前驅。
   • 比較 a[1] < a[5] (20 < 25)，條件成立。
   • 更新 lis_lengths[5] = lis_lengths[1] + 1 = 3
   • 更新 previous_index[5] = 1，表示 a[1] 是 a[5] 的前驅。
   • 比較 a[2] < a[5] (30 < 25)，條件不成立。
   • 比較 a[3] < a[5] (5 < 25)，條件成立。
   • 比較 a[4] < a[5] (15 < 25)，條件成立。
   • 最終更新 lis_lengths[5] = lis_lengths[4] + 1 = 3（保持不變）
   • 狀態更新：
     • lis_lengths = [1, 2, 3, 1, 2, 3]
     • previous_index = [-1, 0, 1, -1, 0, 1]

找到最長 LIS 的長度與序列

1. LIS 長度：max(lis_lengths) = 3
2. LIS 結尾索引：max_index = lis_lengths.index(3) = 2（或 5）
3. 回溯求 LIS：
   • 從 max_index = 2 開始回溯 previous_index：
     • a[2] = 30，前驅 a[1] = 20，前驅 a[0] = 10。
   • LIS 結果為 [10, 20, 30]。

最終結果輸出

最長遞增子序列的長度是: 3
最長遞增子序列為: [10, 20, 30]

另一條序列是 [5, 15, 25]。