Python：最大サブアレイSum

Question

私は今、Pythonの学習を始めようとしています。そのため、関数については分かりません。しかし、私は最大のサブアレイの問題を発見し、私が処分した数少ない単純な論理コマンドでそれを解決しようとしていました。私は立ち往生しており、問題は私の論理にあり、構文的ではないことはほぼ確実ですが、間違いかもしれません。ここに私のコードは、これまでで...

def maxSequence(arr): #Latest attempt, some issue. 
    old_arr = [] 
    print(arr) 
    while old_arr != arr: 
    old_arr = arr 
    if arr[0] > 0 and arr[len(arr)-1] > 0: #For when both sides are positive, need to be sure there is not anything to be gained by eliminating some side section 
     new_sum = 0 
     y=0 
     while new_sum >= 0 and y != -1: 
     new_sum = sum(arr[:y]) 
     y=y+1 
     if y == len(arr)-1: 
      y=-1 
     if y != -1: 
     arr = arr[y-1:] 
     print("left %s" %(new_sum)) 
     print("left %s" % (arr)) 
     new_sum = 0 
     y = 0 
     while new_sum >= 0 and y != -1: 
     new_sum=sum(arr[(len(arr)-y):]) 
     y=y+1 
     if y == len(arr)-1: 
      y=-1 
     if y != -1: 
     arr = arr[:len(arr)-y+1] 
     print("right %s" %(new_sum)) 
     print("right %s" % (arr)) 
    else: 
     while arr[0] < 0 or arr[len(arr)-1] < 0: #To eliminate negatives on sides 
     if arr[0] < 0: 
     arr = arr[1:] 
     if arr[len(arr)-1] < 0: 
     arr = arr[:len(arr)-1] 
     print("negative %s" % (arr)) 
    print(arr) 
    print(sum(arr)) 

様々な印刷機能は、プログラムによって行われた各決定を示し、そして私はそれがループを実行するときに何が起こっているかを視覚化するのに役立ちます。

それはリストに

[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26] 

を与えられたとき、それは長いポスト申し訳ありません

[21, 20, 30, -29, 17, 9, -19, 28, 11, 6] 

にリストが低減された、94の合計で終わり105の正しい結果を与えていませんしかし、私は何が間違っているのか分かりません。ご協力いただきありがとうございます。

上記のリストが入力として与えられたときの出力ですが、私は各ステップを見て、リストからのすべての削除が論理的に見えますが、どのようにして1つのエンディング誰かが私の理解を助けてくれたら、本当にありがとう！

[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, 
-27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, 
-25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26] 
negative [26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, 
-8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 
11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17] 
left -22 
left [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, 
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17] 
right -8 
right [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, 
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6, -13, -13, 25, -22, 8, 9, -4] 
negative [3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, 
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6, -13, -13, 25, -22, 8, 9] 
left -3 
left [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, 
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, 
-13, -13, 25, -22, 8, 9] 
right -5 
right [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, 
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, 
-13, -13, 25] 
negative [15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, 
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, 
-13, -13, 25] 
left -5 
left [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6, -13, -13, 25] 
right -1 
right [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6] 
negative [1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 
6] 
left -13 
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6] 
right -12 
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27] 
left 84 
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27] 
right -8 
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6] 
left 77 
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6] 
right 53 
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6] 
[21, 20, 30, -29, 17, 9, -19, 28, 11, 6] 
94 

Answer 1

私は少しの例とあなたのアルゴリズムで間違っているものを説明します。

入力が

[2, -3, 1] 

[2]が明らかに最大サブアレイであると言います。

[2, -3, 1] 
^^^^^ 

、それは[2, -3]を削除することによって、アレイの合計を増加させることができることを参照してください。ただし、あなたのアルゴリズムは、この部分を見ていきます。

最大サブアレイが負のサブアレイの一部である場合、両端から負のサブアレイを削除することは間違っています。よりスマートなアルゴリズムが必要です。

Answer 2

なぜだけではなく、使用O（n）時間を要するKadaneのアルゴリズム？

Kadaneのアルゴリズム（DP）：

Initialize: 
    max_so_far = 0 
    max_ending_here = 0 

Loop for each element of the array 
    (a) max_ending_here = max_ending_here + a[i] 
    (b) if(max_ending_here < 0) 
      max_ending_here = 0 
    (c) if(max_so_far < max_ending_here) 
      max_so_far = max_ending_here 
return max_so_far