連續增加的子序列

Question

我正在嘗試查找列表中最長的連續增加的子序列。

例如：如果我有一個列表：[1,2,3,0,2,3,5,6,7,1,4,5,6,9]輸出應爲[0,2,3,5,6,7]，因爲它是長於[1,2,3]和[1,4,5,6,9]

我寫我的代碼，我可以打破我的名單成更小的列表（如上圖所示），但只有計算每個較小序列的長度。但我需要做的是輸出最長的子序列，而不是它的長度，因爲我似乎無法做到這一點（我不斷收到邏輯錯誤）的一些奇怪的原因。

所以這裏是我的代碼，這是我試圖實現它的一種方式，我面臨的問題是當temp到arr2時。請幫我解決這個問題，並建議一個替代和更有效的算法，我可以使用它？

arr = [1,2,3,0,2,3,5,6,7,1,4,5,6,9] #original list 
arr2 = [] #empty list (2 dimension) 
counter = 1 

temp = [] #temporary list 
for x,y in enumerate(arr): 

    if(x == 0): 
     temp.append(y) #append first value to temp 
    else: 

     if(arr[x] > arr[x-1]): #if value of x is greater than previous one: 

      counter += 1 #increase counter if condition met 
      temp.append(y) #append list value to temp 

     else: #if value of x is not greater than previous one: 

      print(temp) 
      arr2.append(temp) #append entire temp list to arr2 
      temp[:] = [] #clear the temp list 
      temp.append(y) #append the new lowest value to temp 
      counter = 1 #reset counter 

print(arr2) 

Answer 1

首先，您要複製到當你寫的列表的引用：
arr2.append(temp)
然後你更新列表temp，所以你最終對arr2中的相同列表的幾處引用。 你應該把列表，而不是一個副本：
arr2.append(temp[:])

而且，你永遠不會複製找到這樣你缺少一個在arr2最後的序列。 你可以做到這一點的for循環之外，例如：

 else: #if value of x is not greater than previous one: 

      print(temp) 
      arr2.append(temp) #append entire temp list to arr2 
      temp[:] = [] #clear the temp list 
      temp.append(y) #append the new lowest value to temp 
      counter = 1 #reset counter 

arr2.append(temp[:]) 
print(arr2) 

通過以上，你會得到[[1, 2, 3], [0, 2, 3, 5, 6, 7], [1, 4, 5, 6, 9]]當您打印arr2。然後，它只是一個選擇裏面最長的列表的問題。

Answer 2

首先讓l0在給定的名單：

l0 = [1,2,3,0,2,3,5,6,7,1,4,5,6,9] 

接下來，我們創建的l0所有連續子列表清單，但我們扔掉未增加（見if的那些結束生成器對象的語句）。

l1 = [l[i:j] for i in xrange(len(l)-1) for j in xrange(i,len(l0)) if l[i:j] == sorted(l[i:j])] ## all substrings that are increasing. 

你要求的是最長的這樣的子字符串。所以，只返回那些長度的最大值：

print max([len(l) for l in l1]) 

Answer 3

解決方案沒有創建一個新的列表。

def max_inc_seq(seq): 
    first_ret = first_curr = 0 
    last_ret = last_curr = 0 
    for i in range(1, len(seq)): 
     if seq[i] > seq[i-1]: 
      last_curr = i # move pointer to the item 
     else: 
      last_curr = first_curr = i # reset pointers 
     len_curr = last_curr - first_curr 
     len_ret = last_ret - first_ret 
     if len_curr > len_ret: # the current seq. longer what longest for now 
      first_ret = first_curr 
      last_ret = last_curr    
    return seq[first_ret:last_ret+1] 

試驗max_inc_seq：

seqs = (
    ([0, 1, 2], [0, 1, 2]), 
    ([1,2,3,0,2,3,5,6,7,1,4,5,6,9], [0, 2, 3, 5, 6, 7]), 
    ([1, 0], [1]), 
    ([-1, 0, 1], [-1, 0, 1]), 
    ([0, 1, 1], [0, 1]), 
    ) 

for seq, test in seqs: 
    ret = max_inc_seq(seq) 
    assert ret == test, "{} != {}".format(ret, test) 

Answer 4

這是爲上述問題的最有效的算法。它的時間複雜度爲O(N)，空間複雜度爲O(1)。

• 從數組開始迭代。

• 檢查下一個元素是否大於當前元素。如果是，則增加數組的結束位置。然後檢查這個長度是否比直到現在遇到的所有時間最大長度更好。如果是，則分別用當前開始和結束初始化beststart和bestend。

• 如果下一個元素不大於當前元素，則重新初始化開始和結束位置。

下面是一個簡單的實現上述算法：

arr = [1,2,3,0,2,3,5,6,7,1,4,5,6,9] #original list 

l = len(arr) # l stores the length of the array 
i = 0 # initialize i, iterate from left of the array 

max = 1 # the max is always a one element array 

start = 0 # initialize start at the beginning of the array 
end = 0 # initialize end at the beginning of the array 

beststart = 0 # initialize beststart at the beginning of the array 
bestend = 0 # initialize bestend at the beginning of the array 

while i<l: 
    if i+1 < l and arr[i+1]>arr[i]: 
     end = end + 1 # increment end, as we found a longer array 
     if (end-start+1) > max: 
      max = (end - start + 1) # update max 
      beststart = start # update beststart as we have the longest array till this point 
      bestend = end # update bestend as we have the longest array till this point 
    else: 
     start = i+1 # re-initialize start 
     end = i+1 # re-initialize end 

    i = i + 1 

print (arr[beststart:bestend+1]) # print the longest array 

輸出：[0, 2, 3, 5, 6, 7]