Kadane's Algorithm for Maximum Subarray Problem

Kadane's Algorithm for Maximum Subarray Problem

I just copied the below algorithm from wikipedia for reference. For more information, you can always go to

http://en.wikipedia.org/wiki/Maximum_subarray_problem

Kadane's Algorithm(array[1..n])

begin

(maxSum, maxStartIndex, maxEndIndex) := (-INFINITY, 0, 0)

currentMaxSum := 0

currentStartIndex := 1

for currentEndIndex := 1 to n do

currentMaxSum := currentMaxSum + array[currentEndIndex]

if currentMaxSum > maxSum then

(maxSum, maxStartIndex, maxEndIndex) := (currentMaxSum, currentStartIndex, currentEndIndex)

endif

if currentMaxSum < 0 then

currentMaxSum := 0

currentStartIndex := currentEndIndex + 1

endif

endfor

return (maxSum, maxStartIndex, maxEndIndex)

end

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

This algorithm is for an 1D array, in our case this is an 2D array in input.

Hey.
I think it's very different :)

yes it is , think you any way

Laisser un commentaire

Veuillez ouvrir une session pour ajouter un commentaire. Pas encore membre ? Rejoignez-nous dès aujourd’hui