Created
August 20, 2015 12:30
-
-
Save aldraco/9e5ffbba164c8b50d92b to your computer and use it in GitHub Desktop.
Greedy max subarray algorithm (Kandane)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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