Skip to content

Instantly share code, notes, and snippets.

@calvinfroedge
Created April 1, 2014 00:34
Show Gist options
  • Save calvinfroedge/9905412 to your computer and use it in GitHub Desktop.
Save calvinfroedge/9905412 to your computer and use it in GitHub Desktop.
Find the max slice of an array
function sum(a,b){
return a+b;
}
Array.prototype.min = function(){
return Math.min.apply(null, this);
}
function maxSlice(arr){
//Are there any negative numbers? If not, the entire array is the greatest segment.
if(arr.min() >= 0) return arr;
//Is array length 1? Just return
if(arr.length == 1) return arr;
//Find the entire sum
var total = arr.reduce(sum);
//Find the min index
var mindex = arr.indexOf(arr.min());
//If mindex at the end
if(mindex == arr.length - 1) return maxSlice(arr.slice(0, -1));
//If mindex at beginning
if(mindex == 0) return maxSlice(arr.slice(1));
//Split the array into two chunks
l = maxSlice(arr.slice(0,mindex));
lsum = l.reduce(sum);
r = maxSlice(arr.slice(mindex+1));
rsum = r.reduce(sum);
//Return the greatest of the total or the chunks before / after the min
if(total > lsum && total > rsum){
return maxSlice(arr);
} else {
return (rsum > lsum) ? r : l;
}
}
print(maxSlice([1, -3, 4, -2, 2]));
print(maxSlice([2, 3, 1, -5, 2]));
print(maxSlice([-23, -14, 4, 3, 2, -21, 14, -32, 40]));
print(maxSlice([-17, 14, 21, 2, -38, 22, 8, 7, 9, -38]));
print(maxSlice([-100, -200, 50, -50, 23, 22, 14, 1]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment