kadane algorithm

kadane algorithm

 public class Kadane {

double maxSubarray(double[] a) {

double max_so_far = 0;
double max_ending_here = 0;

for(int i = 0; i < a.length; i++) {
max_ending_here = Math.max(0, max_ending_here + a[i]);
max_so_far = Math.max(max_so_far, max_ending_here);
}

return max_so_far;

}

}

this code returns the sum of maximum sub array, but i am looking to return the array which has the maximum sum! logical help appreciated.

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

It's already posted http://software.intel.com/fr-fr/forums/showthread.php?t=101083

but here it is again,

basically, you add each element a[i] to the max_ending_here if the sum is greater than zero then you compare it with the max_so_for if is also greater (we found a new maximum):

then the start_indexequals start(more on that later) and the end_index is i (your position in the array at this iteration

so when do you change the start (used later to set start_index when we have a larger sum)
at the beginning you assume that the best start position is the first element
but whenever max_ending_here goes below zero which means there are more negative values than positive values in the portion ending at the ith element
then we should leave this and start from the next element i.e. start = i + 1

Notice that we change start whenever max_ending_here goes below zero but we update start_index when we find a better sum because consider this example {10,20,30,-10,-30,-40}

the algorithm will start adding till the maxsum = 10+20+30 = 60 (start_index = 0, end_index = 2)
then the negative numbers will start decreasing max_ending_here to 50, 20, -20
at this point start = i + 1 = 6 if we changed start_index we would lose the maxsum but because of this separation we are still able to find the best solution

Kadane's algorithm /* maximum subarray a[k..l] of a[1..n] */ int max_so_far = 0, max_ending_here = 0;

int i;

int start = 0;

for(i = 0; i < size; i++)

{

max_ending_here = max_ending_here + a[i];

if(max_ending_here < 0)

{ //extend the algorithm by finding the min

max_ending_here = 0;

start = i + 1;

}

/* Do not compare for all elements. Compare only

when max_ending_here > 0 */

else if (max_so_far < max_ending_here)

{

k = start;

k = i;

max_so_far = max_ending_here;

}

}

return max_so_far;

Connectez-vous pour laisser un commentaire.