Somme maximale des sous-séquences :Marc Weiss :
-
28-09-2020 - |
Question
Dans la partie en surbrillance ci-dessous, comment Weiss conclut-il que le tableau commençant à un index arbitraire « p » et se terminant par « j » ne peut jamais être plus grand que le tableau commençant par « i » et se terminant par « p-1 » ?
Par son propre exemple (la boucle interne de l'algorithme 2 illustré ci-dessous), cela est manifestement faux.
Soit i = 0 et j = 3.
Soit a[ 0 ] = -14, a[ 1 ] = -4, a[ 2 ] = -2, a[ 3 ] = -1.
Si p = 2, la somme des sous-séquences de « p » à « j » est clairement plus grande que « i » à « p-1 ».
Plus inquiétant encore est M.Weiss semble tirer une hypothèse de nulle part (« j est le premier indice qui fait que la sous-séquence commençant à l'indice i devient négative ») alors que rien dans ce qui précède ne pourrait impliquer cela !En effet, Weiss ne mentionne que la "détection" de la somme des sous-séquences négative entre les indices "i" et "j", mais jamais là où la source de cela ne pourrait que se produire.D'où ça vient ?
Merci pour toute aide!
La solution
Je pense que vous ne savez pas quel algorithme il décrit.Sa description ne concerne pas l'algorithme 2 mais l'algorithme 4, où un index imaginaire i
en réintroduit.
Permettez-moi d'écrire cet algorithme avec cet index pour que ce soit clair :
maxSubSum(array a):
maxSum = 0, thisSum = 0;
i = 0;
for j going from 0 to length(a)-1:
thisSum += a[j];
if thisSum > maxSum:
maxSum = thisSum;
else if thisSum < 0:
i = j+1;
thisSum = 0;
return maxSum;
Maintenant, vous pouvez voir que dans cet algorithme, chaque fois que thisSum < 0, alors j
est en effet le "premier index qui provoque la sous-séquence commençant à l'index i
devenir négatif", et le reste de l'affirmation suit.Notez en particulier que l'exemple que vous avez donné ne peut pas se produire avec cet algorithme (vous n'aurez jamais i=0
et j=3
dans ce cas).