Python: Maximum Subarray Sum

Question

Je viens d'essayer de commencer à apprendre Python aujourd'hui, donc je ne suis pas au courant quand il s'agit de ses fonctions. Cependant, j'ai trouvé le problème du sous-réseau maximum, et j'ai voulu essayer de le résoudre avec les quelques commandes logiques simples dont je dispose. Je me suis coincé, et je suis presque certain que le problème est dans ma logique et non pas syntaxique, bien que je puisse très bien me tromper. Voici mon code jusqu'à présent ...

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)) 

Les différentes fonctions d'impression montrent chaque décision prise par le programme, et me aider à visualiser ce qui se passe car il exécute les boucles.

Il ne donne pas le résultat correct de 105 quand donné la liste

[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] 

Il se termine par une somme de 94, après avoir réduit la liste à

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

Désolé pour le long post , mais je ne peux pas comprendre ce que je fais mal. Merci d'avance pour votre aide!

Voici la sortie lorsque la liste ci-dessus est donnée en entrée, j'ai parcouru et regardé chaque étape, et chaque élimination de la liste me semble logique, je ne sais pas comment on pourrait se retrouver avec une fin somme de 105. Si quelqu'un pouvait m'aider s'il vous plaît à comprendre, je l'apprécierais vraiment!

[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

Je vais montrer ce qui ne va pas avec votre algorithme avec un petit exemple.

Dites l'entrée est

[2, -3, 1] 

[2] est clairement le sous-tableau maximale. Cependant, votre algorithme se penchera sur cette partie:

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

et de voir qu'il peut augmenter la somme du tableau en supprimant [2, -3].

La suppression des sous-matrices négatives des extrémités ne convient pas si la sous-matrice maximale fait partie d'une sous-matrice négative. Vous aurez besoin d'un algorithme plus intelligent.

Answer 2

Pourquoi ne pas utiliser l'algorithme de Kadane qui prend O (n) ??

algorithme de 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