Skip to content

Instantly share code, notes, and snippets.

@jremmen

jremmen/submax.js

Created July 2, 2014 23:14
Show Gist options
  • Save jremmen/f307ef21cc6fb22c06d1 to your computer and use it in GitHub Desktop.
Save jremmen/f307ef21cc6fb22c06d1 to your computer and use it in GitHub Desktop.
Download ZIP
js: maximum sub array in linear time
Raw
submax.js
// O(n)
Array.prototype.submax = function() {
var max = sum = 0;
for(var i = 0, l = this.length; i < l; i++) {
sum = Math.max(sum + this[i], 0);
max = Math.max(max, sum);
}
return max;
}
@yckart
Copy link

yckart commented May 7, 2016

var max = sum = 0; should be var max = 0, sum = 0;. Otherwise, sum will be global.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment