從一個序列中提取最大長度的子序列[PYTHON]

Question

我有一個值序列[1,2,3,4,1,5,1,6,7]，我必須找到最長的子序列增加長度。但是，一旦達到低於前一個數字的數字，該功能就需要停止計數。這種情況下的答案是[1,2,3,4]。因爲在重置之前它有4個值。我將如何爲此編寫Python代碼？

注意：尋找「最長的增長子序列」似乎是一個常見的挑戰，因此在線搜索我找到了很多可以計算整個序列長度的解決方案，並返回一個遞增值的子序列，忽略任何減少，所以在這種情況下，它會返回[1,2,3,4,5,6,7]。這不是我正在尋找的。

它需要對每個子序列進行計數，並在達到低於前一個數字的數字時重置計數。然後它需要比較所有計數的子序列，並返回最長的子序列。

在此先感謝。

Answer 1

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

def findsub(a): 
    start = -1 
    count = 0 
    cur = a[0] 
    for i, n in enumerate(a): 
    if n is cur+1: 
     if start is -1: 
     start = i - 2 
     count=1 
     count+=1 
     cur = n 
    if n < cur and count > 1: 
     return [a[j] for j in range(start,start+count+1)] 


print findsub(b) 

一個有點草率的算法，但我相信它做你想做的。通常我不會簡單地向你展示代碼，但我懷疑這是你想要的，我希望你可以從中學習，並從你學到的東西中創建你自己的代碼。

一個稍顯好看的方式，因爲我不喜歡的是：

b = [1,2,0,1,2,3,4,5] 

def findsub(a): 
    answer = [a[0]] 
    for i in a[1:]: 
    if answer[-1] + 1 is i: 
     answer.append(i) 
    if not len(answer) > 1: 
     answer = [i] 
    elif i < answer[-1] and len(answer) > 1: 
     return answer 
    return answer 



print findsub(b) 

Answer 2

你需要做到以下幾點：

1. 創建一個功能W給定一個列表，返回索引最後一項從列表的開始處開始並不嚴格增加。

   • 例如，給出以下列表：[1,2,3,4,1,2,3], [4,2,1], [5,6,7,8]，它應該返回4，1，4，分別爲每個列表

2. 創建一個變量maxim和值設置爲0

3. 重複以下操作，直到列表爲空
   • 打電話給你的清單上的功能W，讓我們調用的返回值x
   • 如果x大於maxim
     • 設置maxim到x
     • 在這一點上，如果你想存儲這個序列，就可以使用list-slice notation以獲取包含序列的列表部分。
   • 從列表中刪除列表中的部分

最後，打印maxim如果你保存你的包含最長序列表的部分，然後打印的最後一個你有

Answer 3

考慮一個函數，可以生成所有可能的升序子序列，您將從一個空列表開始，添加項目直到一個元素少於（或等於？）前一個節點（yield）的子序列和r帶有新的子序列。

一個實現用發電機可能是這樣的：

1. 要完成發電機的StopIteration需求是 提出的，所以我們可以只：
   有關處理空序列的

   def all_ascending_subsequences(sequence): 
       #use an iterator so we can pull out the first element without slicing 
       seq = iter(sequence) 
   
       try: #NOTE 1 
        last = next(seq) # grab the first element from the sequence 
       except StopIteration: # or if there are none just return 
        #yield [] #NOTE 2 
        return 
   
       sub = [last] 
       for value in seq: 
        if value > last: #or check if their difference is exactly 1 etc. 
         sub.append(value) 
        else: #end of the subsequence, yield it and reset sub 
         yield sub 
         sub = [value] 
        last = value 
   
       #after the loop we send the final subsequence 
       yield sub 
   

   兩個音符讓從next(seq) propegate了一個 - 然而，當from __future__ import generator_stop是 效應會導致RuntimeError所以要兼容未來我們 需要ŧ o趕上它並明確return。

2. 正如我寫它通過一個空列表 all_ascending_subsequences將不會產生任何值，這可能不是 是所需的行爲。隨意取消註釋yield []至 傳遞空列表時生成一個空列表。

然後，你可以得到最長的通過與key=len

b = [1,2,3,4,1,5,1,6,7] 

result = max(all_ascending_subsequences(b),key=len) 
print("longest is", result) 

#print(*all_ascending_subsequences(b))