Kadane's 1D algorithm

Kadane's 1D algorithm

Here is Kadane's 1D algorithm O(N3)

Kadane's algorithm /* maximum subarray a[k..l] of a[1..n] */

(k; l) := (0; 0); s := -inf; t := 0; j := 1;

for i:=1 to n do begin

t := t + a[i];

if t > s then begin (k; l) := (j; i); s := t end;

if t < 0 then begin t := 0; j := i + 1 end

end

1 contribution / 0 nouveau(x)
Reportez-vous à notre Notice d'optimisation pour plus d'informations sur les choix et l'optimisation des performances dans les produits logiciels Intel.