長さだけでなく実際の最長増加サブシーケンスを印刷する方法

Question

私はLongest Increasing SubsequenceのGeeksforGeeksコードを見直しています。長さだけでなく、実際に最も長くなるサブシーケンスを印刷する方法を理解しようとしています。

私は何とか最大のインデックスを格納し、その配列から実際の数値をプリントアウトする必要があることを知っています...私はそれを実装するのに問題があります。次のように

G4Gのウェブサイトからのコードは次のとおりです。

# Dynamic programming Python implementation of LIS problem 

# lis returns length of the longest increasing subsequence 
# in arr of size n 
def lis(arr): 
    n = len(arr) 

    # Declare the list (array) for LIS and initialize LIS 
    # values for all indexes 
    lis = [1]*n 

    # Compute optimized LIS values in bottom up manner 
    for i in range (1 , n): 
     for j in range(0 , i): 
      if arr[i] > arr[j] and lis[i]< lis[j] + 1 : 
       lis[i] = lis[j]+1 

    # Initialize maximum to 0 to get the maximum of all 
    # LIS 
    maximum = 0 

    # Pick maximum of all LIS values 
    for i in range(n): 
     maximum = max(maximum , lis[i]) 

    return maximum 
# end of lis function 

# Driver program to test above function 
arr = [10, 22, 9, 33, 21, 50, 41, 60] 
print "Length of lis is", lis(arr) 
# This code is contributed by Nikhil Kumar Singh 

Answer 1

あなたが指摘したように、LISの指標も同様に保存する必要があります。

これは、追加の配列prevを導入することによって行うことができます。元のコードでは、lis(n)は、nで終わるLISの長さを表し、nで終わるLIS内のnの直前のインデックス番号を表すprev(n)（つまり、LISの2番目の最後のインデックス番号）を返します。 nの長さは1であり、単にprev(n) = nと定義します。

lis(n)の値を更新するたびに、prev(n)もそれに応じて更新する必要があります。下記の拡張コードを参考にしてください：

# Dynamic programming Python implementation of LIS problem 

# lis returns length of the longest increasing subsequence 
# in arr of size n 
def lis(arr): 
    n = len(arr) 

    # Declare the list (array) for LIS and initialize LIS 
    # values for all indexes 
    lis = [1]*n 

    prev = [0]*n 
    for i in range(0, n): 
     prev[i] = i 

    # Compute optimized LIS values in bottom up manner 
    for i in range (1 , n): 
     for j in range(0 , i): 
      if arr[i] > arr[j] and lis[i]< lis[j] + 1: 
       lis[i] = lis[j]+1 
       prev[i] = j 

    # Initialize maximum to 0 to get the maximum of all 
    # LIS 
    maximum = 0 
    idx = 0 

    # Pick maximum of all LIS values 
    for i in range(n): 
     if maximum < lis[i]: 
      maximum = lis[i] 
      idx = i 

    seq = [arr[idx]] 
    while idx != prev[idx]: 
     idx = prev[idx] 
     seq.append(arr[idx]) 

    return (maximum, reversed(seq)) 
# end of lis function 

# Driver program to test above function 
arr = [10, 22, 9, 33, 21, 50, 41, 60] 
ans = lis(arr) 
print "Length of lis is", ans[0] 
print "The longest sequence is", ", ".join(str(x) for x in ans[1])