サブシーケンスが連続的に増加しています

Question

リスト内で最も長くなっている連続したサブシーケンスを検索しようとしています。

例：それは長い[1,2,3]以上と[1,4,5,6,9]

私は（上記のように）私は小さいリストに私のリストを破ることができる私のコードを書かれている

だけだとして[1,2,3,0,2,3,5,6,7,1,4,5,6,9]出力は[0,2,3,5,6,7]をする必要があります：私は、リストを持っている場合より小さい各シーケンスの長さを計算する。しかし、私がしなければならないのは、長さではなく最長のサブシーケンスを出力することです。それを行うことができないような奇妙な理由のために（私は論理的なエラーを出し続けます）。

これは私のコードです。これは私が実装しようとした方法の1つで、私が直面している問題は、を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の1が欠けているように、最後に見つかったサブシーケンスをコピーすることはありません。 あなたが例えばforループの外でそれを行うことができます：あなたはarr2を印刷する時には、上記で

 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]]を取得します。 次に、内部で最長のリストを選択することだけです。

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

新しいリストを作成せずに解決します。 max_inc_seqため

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] 

テスト：

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)です。

• アレイの先頭から反復する。

• 次の要素が現在の要素より大きいかどうかを確認します。 yesの場合は、配列の終了位置をインクリメントします。次に、この長さが現在までに遭遇した全時間最大長よりも優れているかどうかを確認します。はいの場合は、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]