Skip to content

Instantly share code, notes, and snippets.

@aldraco
Created August 20, 2015 12:30
Show Gist options
  • Save aldraco/9e5ffbba164c8b50d92b to your computer and use it in GitHub Desktop.
Save aldraco/9e5ffbba164c8b50d92b to your computer and use it in GitHub Desktop.
Greedy max subarray algorithm (Kandane)
function Kandane(arr) {
// tracking the best (best sum, best index) possible indexes to get the highest list
// must be contiguous so we only update the indexes and max sum when we find a higher list
// otherwise, we track the potential (current) until it beats the best
var current_sum = 0,
best_sum = 0,
current_index = -1,
best_start = -1,
best_end = -1;
var len = arr.length;
for (var i = 0; i < len; i++) {
// look at each value and see if it contributes to a higher sub array
// what is our potential here?
var new_val = current_sum + arr[i];
// we are only looking for positive values.
if (new_val > 0) {
if (current_sum === 0) {
// then we started over on the previous step
// update the current 'start' index
current_index = i;
}
// either way update the current sum to compare to best
// as long as it's positive
current_sum = new_val;
} else {
// if it's negative then we must start over
// since we want contiguous values only.
current_sum = 0;
}
// now compare the current sum to the best sum
if (current_sum > best_sum) {
// update your indexes
best_start = current_index;
best_end = i;
// and the values
best_sum = current_sum;
}
}
// now return the sub array
var answer = arr.slice(best_start, best_end + 1);
return answer;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment