最大サブアレイを見つけようとする私のアルゴリズムがなぜ機能しないのですか？

Question

私は本の「アルゴリズムの紹介」（第4章）に従って、この最大サブアレイアルゴリズムを実装しようとしています。実行することはできますが、結果は正しくありません。私はここで論理的な問題を見つけることができません。ありがとうございました。

def find_max_crossing_subarray(A,low,mid,high):  
    leftSum=float('-inf') 
    result=0     ## left_max_sum of midpoint 
    maxLeft=0 
    maxRight=0 

    for i in range(mid,low,-1): 
     result=result+A[i]   
     if result>leftSum: 
      leftSum=result 
      maxLeft=i 

    rightSum=float('-inf') 
    result2=0      ##right_max 
    for j in range(mid+1,high,1): 
     result2=result2+A[j] 
     if result2>rightSum: 
      rightSum=result2 
      maxRight=j 
    Result=result+result2   
    return maxLeft,maxRight,Result 


def find_maximum_subarray(A,low,high): 
    if low==high: 
     return low, high, A[low] 
    else: 
     mid=(low+high)//2 
     leftLow,leftHigh,leftSum=find_maximum_subarray(A,low,mid) 
     rightLow,rightHigh,rightSum=find_maximum_subarray(A,mid+1,high) 
     crossLow, crossHigh,crossSum=find_max_crossing_subarray(A,low,mid,high) 
     if leftSum>=rightSum and leftSum>=crossSum: 
      return leftLow,leftHigh,leftSum 
     elif rightSum>=leftSum and rightSum>=crossSum: 
      return rightLow, rightHigh, rightSum 
     else: 
      return crossLow,crossHigh,crossSum 

A=[1,2,30,21] 
print (find_maximum_subarray(A,0,len(A)-1)) 

Answer 1

これが見つかりました！

find_max_crossing_subarrayにおいて

、代わりにrange(mid,low,-1)使用range(mid,low-1,-1)、代わりrange(mid+1,high,1)使用range(mid+1,high+1,1)します。

さらなる説明：

rangedocumentationから：

ステップが肯定的である場合は、最後の要素は、最大のスタートです+ iの停止よりもステップ 少ないです*; stepが負の場合、最後の要素はstopよりも小さい start + i * stepの最小値です。

つまり、range(0, 5)は、[0, 1, 2, 3, 4]となります。

Result値のRyanの修正も参照してください。

Answer 2

lowとmidが同じ場合、forループは機能しません。 forの代わりにforを使用する方が良い選択です。結果も元のバージョンでは間違っています。

def find_max_crossing_subarray(A,low,mid,high): 
    leftSum=float('-inf') 
    result=0     ## left_max_sum of midpoint 
    maxLeft=0 
    maxRight=0 
    i=mid 
    while i>=low: 
     result+=A[i] 
     if result>leftSum: 
      leftSum=result 
      maxLeft=i 
     i-=1 


    rightSum=float('-inf') 
    result2=0 
    j=mid+1     ##right_max 
    while j<=high: 
     result2+=A[j] 
     if result2>rightSum: 
      rightSum=result2 
      maxRight=j 
     j+=1 
    Result=leftSum+rightSum  
    return maxLeft,maxRight,Result 

Answer 3

Kadaneのアルゴリズムは、配列値を介してスキャンから成り、コンピュ各位置で最大値（正の和）は、その位置で終わるサブアレイ。このサブ配列は空の場合（その場合、その合計はゼロ）、または前の位置で終了する最大部分配列より1つ多くの要素で構成されます。アルゴリズムは、を追跡する必要があるのは、の暗黙の開始位置が、合計が負になる最後の位置の直後であるためです。負の合計プレフィックスを削除することによって、より高い合計を常に見つけることができます。

本質的に、最も簡単なアルゴリズムは、配列をループして、現在の値よりも前に存在する可能性のある最大のサブアレイを見つける必要があるソリューションを示します。

アルゴリズムを簡素化するために、負の数を削除して、前回の合計が正の場合の開始インデックスを維持します。これは空の配列に対して配列のいずれかがの最小合計がゼロであるためです。

def mssl(l): 
    best = cur = 0 
    for i in l: 
     cur = max(cur + i, 0) 
     best = max(best, cur) 
    return best 

クレジットの説明のためのWikipediaから：

したがって、あなたはあなたのアルゴリズムを簡素化することができます。

同様の問題は、ユーザからの素晴らしい答えをhereを見つけnneonneo