Skip to content

Instantly share code, notes, and snippets.

@JasonGhent
Created January 7, 2015 16:41
Show Gist options
  • Save JasonGhent/566007027d2eda3b7c89 to your computer and use it in GitHub Desktop.
Save JasonGhent/566007027d2eda3b7c89 to your computer and use it in GitHub Desktop.
Shoddy script for finding max rectangular area under a curve, for histograms in this case.
function maxArea (original, histogram, maxArray) {
if (!histogram) {
histogram = original.slice(0);
}
maxArray = maxArray || new Array(histogram.length);
var currVal = histogram.pop();
if (currVal===0 || !histogram.length) {
maxArray[histogram.length] = currVal;
}
else {
var localMaxes=[],max = 1;
for (var j = currVal; j>0; j--) {
for (var i = histogram.length-1; i >= 0; i--) {
var itrVal = histogram[i];
if (itrVal < currVal) {
localMaxes[j] = max * currVal;
break;
}
else {
max++;
localMaxes[j] = max * currVal;
}
}
}
}
if (!histogram.length) {
return _.max(maxArray);
}
else {
return maxArea(original, histogram, maxArray);
}
}
// #
// # # #
// # # # # # # #
// # # # # # # # #
// 4,3,2,0,2,3,2,2,1
console.log(maxArea([4,3,2,0,2,3,2,2,1]))
//> 8
// #
// # # # #
// # # # # # # #
// # # # # # # # #
// 4,3,2,0,2,3,2,3,1
console.log(maxArea([4,3,2,0,2,3,2,3,1]))
//> 8
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment