Somme maximale des sous-séquences :Marc Weiss :

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!

Answer 1

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