以下に示すのは、最大のサブ配列を返すためのPython2.7のkadaneのアルゴリズムのコードです。正しい最大合計(MSS変数)を取得していますが、指定されたサンプルリストでは、間違ったサブ配列が返されています。誰かが私に理由を説明してもらえますか?
A = [-2,1,-3,4,-1,2,1,-5,4]
M = max(A)
L = len(A)
if(M < 0):
print M
ans = []
subans = []
MSS,subsum,i = 0,0,0
while(i<L):
subans.append(A[i])
subsum = sum(subans)
if(subsum<0):
subans=[]
i+=1
else:
if(subsum>MSS):
MSS=subsum
ans=subans
i+=1
else:
i+=1
print ans
あなたの問題はあなたがそうするとき-
ans=subans
あなただけの参照格納しているsubans
のをans
あなたは内の何かを変更する場合、subans
変更はまたに反映、ans
(彼らは同じ参照されているとおり)。
あなたはのコピー保存する必要がありsubans
中をans
代わりに直接参照を、。
例-
ans = []
subans = []
MSS,subsum,i = 0,0,0
while(i<L):
subans.append(A[i])
subsum = sum(subans)
if(subsum<0):
subans=[]
i+=1
else:
print('subsum - ' + str(subsum))
print('MSS - ' + str(MSS))
if(subsum>MSS):
MSS=subsum
ans=list(subans) #more ways to do this, like subans[:] also works, and copy.copy(subans) , etc.
i+=1
else:
i+=1
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加