Given a 2D array of numbers, find the sub-matrix (a rectangular portion of the array) that has the greatest sum of its constituent elements.
Imagine a sliding window, think of a rectangle moving across the matrix. The top-right corner (p1) and bottom-left corner (p2) define this rectangle. For each position of the rectangle, calculate the total of all the numbers inside it. As the rectangle moves, remember the rectangle with the highest total. After checking all possible rectangle positions, return the sum of the rectangle with the highest total.
matrix = [
[ 1, 2, -1, -4, -20 ],
[ -8, -3, 4, 2, 1 ],
[ 3, 8, 10, 1, 3 ],
[ -4, -1, 1, 7, -6 ]
]
output = float('-inf')
h = len(matrix)
w = len(matrix[0])
for top in range(h):
for left in range(w):
for bottom in range(top, h):
for right in range(left, w):
total = 0
for i in range(top, bottom + 1):
for j in range(left, right + 1):
total += matrix[i][j]
output = max(output, total)
print(output)
const matrix = [
[ 1, 2, -1, -4, -20 ],
[ -8, -3, 4, 2, 1 ],
[ 3, 8, 10, 1, 3 ],
[ -4, -1, 1, 7, -6 ]
];
let output = -Infinity;
const h = matrix.length;
const w = matrix[0].length;
for (let top = 0; top < h; top++) {
for (let left = 0; left < w; left++) {
for (let bottom = top; bottom < h; bottom++) {
for (let right = left; right < w; right++) {
let sum = 0;
for (let i = top; i <= bottom; i++) {
for (let j = left; j <= right; j++) {
sum += matrix[i][j];
}
}
output = Math.max(output, sum);
}
}
}
}
console.log(output);