n個の正と負の数列の連続項の最大和を求めるにはどうすればよいですか？

Question

私はこの問題を半分に分割し、それぞれの最大の合計を見つけることによって解決しようとしていました。私はMegaSortを使いました。しかし、私はどのように記録し、各再帰関数から最大の合計を返すかに固執しています。例えば 、

[1、-3、4、-7、8] - - >最大合計は8（自体の合計）

[5,5、-3,6-、でなければなりません10] - >最大の合計は5 + 5 +（-3）+ 6 = 13であるべきである

[3、-9、10、5] - >最大和は10 + 5 = 15

def find_max(seq): 
    if len(seq) == 1: 
     if(seq[0] > sum): 
      sum = seq[0] 
     return seq 
    else: 
     mid = len(seq)//2 
     left = [:seq] 
     right = [seq:] 
     find_max(left) 
     find_max(right) 

あります

Answer 1

あなたの質問がアルゴリズムそのものではなく、Pythonで実装する方法（そして私はPythonを知らない）について理解しているので、この回答が助けになるかどうかはわかりません。しかし、助けを求めずに実装できる別のアルゴリズムがあります。このアルゴリズムは合計を計算するだけで、その合計を返すシーケンスではないことに注意してください（これがわかっている限り、あなたが望むものです）。ここにCのような擬似コードソリューションがあります：

int findMax(sequence, length) { 

    int maxSumStartingAt[length]; 
    maxSumStartingAt[length - 1] = sequence[length-1]; 

    for(int i=length-2; i >= 0; i--) { 
     int tempSum = sequence[i] + maxSumStartingAt[i+1]; 
     if (sequence[i] > tempSum) { 
      maxSumStartingAt[i] = sequence[i]; 
     } else { 
      maxSumStartingAt[i] = tempSum; 
     } 
    } 

    int maxSum = maxSumStartingAt[0]; 
    for(int i = 1; i < length; i++) { 
     if (maxSum < maxSumStartingAt[i]) { 
      maxSum = maxSumStartingAt[i]; 
     } 
    } 

    return maxSum; 
} 

ここでは、このソリューションのしくみを説明します。

1）最大和を生じる部分列はあるインデックスiで始まらなければならないので、すべてのインデックスiについて、iで始まる連続する要素の最大和を計算することが考えられる。結果はこれらの合計の間の最大値になります。

2）ここで、最大の合計をもたらす要素の部分列がインデックスiから始まり、インデックスi + 1で始まる部分列の連続する要素の最大の合計がxだった場合、希望の合計を計算しますか？それは単に我々は、すべてのインデックスのインデックスiから始まる最大の合計を計算するために、この情報を使用することができます

sequence[i] + x 

sequence[i] 

と

の間で最大になり、私：私たちは、シーケンスの最後の要素から始まります我々は0から索引付けを開始した場合、別名

sequence[length-1] 

私はmaxSumStartingAt [長さ-1]を呼ぶことにします。このインデックスから始まり、最大合計は、何ですか？これは、1要素配列であるので それ自体

sequence[length - 1] 

ほかならなることはできません。そして、インデックスの長さ-2から始まる最大の合計は何ですか？ 3 - それは

sequence[length-2] 

と

sequence[length-2] + maxSumStartingAt[length-1] 

そして、何最大の合計は、インデックスの長さで起動している間の最大ですか？ここでも、それは

sequence[length-3] 

と

sequence[length-3] + maxSumStartingAt[length-2] 

間の最大だ私たちは、シーケンスのすべてのインデックスにこの式を適用することができ、最終的に我々は、インデックス0に取得し、私たちはジェネリックから始まる最大の合計を持っていますインデックスごとにインデックスi。これは、ソリューションの最初のforループが行うこととまったく同じです。この時点で、計算された合計の最大値が求められます（これは、ソリューションの2番目のforループと同じです）。この最大値が結果です。

解決策に1つのメモ。あなたが投稿したコードを判断できないので、私はPythonを知らないので、あなたが質問に書いたことを正確に行うと（すなわち、シーケンスを2つの半分に分割し、半分ごとに最大の合計を計算し、これらの2つの値の間にあるシーケンスによって最大の合計が得られる場合をカバーしないため、機能しません。

Answer 2

def largestSum(arr): 
    curr = arr[0] 
    lsum = arr[0] 

    if len(arr) <= 1: 
    return arr 

    for i in range(1, len(arr)): 
    curr = max(arr[i], curr + arr[i]) 

    if curr > lsum: 
     lsum = curr 
    return lsum 

largestSum([-2,3,2,-1])