function findMaxCrossingSubarray(arr, low, mid, high) {
let leftSum = -Infinity;
let sum = 0;
let maxLeft = null;
for (let i = mid - 1; i >= low; i--) {
sum += arr[i];
if (sum > leftSum) {
leftSum = sum;
maxLeft = i;
}
}
let rightSum = -Infinity;
let maxRight = null;
sum = 0;
for (let j = mid; j < high; j++) {
sum += arr[j];
if (sum > rightSum) {
rightSum = sum;
maxRight = j;
}
}
return [maxLeft, maxRight, leftSum + rightSum];
}
function findMaximumSubarray(arr, low, high) {
if (high === low + 1) return [low, high, arr[low]];
else {
const mid = parseInt((low + high) / 2, 10);
const [leftLow, leftHigh, leftSum] = findMaximumSubarray(arr, low, mid);
const [rightLow, rightHigh, rightSum] = findMaximumSubarray(arr, mid, high);
const [crossLow, crossHigh, crossSum] = findMaxCrossingSubarray(arr, low, mid, high);
if (leftSum >= rightSum && leftSum >= crossSum) return [leftLow, leftHigh, leftSum];
else if (rightSum >= leftSum && rightSum >= crossSum) return [rightLow, rightHigh, rightSum];
else return [crossLow, crossHigh, crossSum];
}
}
arr = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
