Maximum Submatrix Sum

1 <= N, M <= 1000
-109 <= A[i][j] <= 10^9

The first argument is a 2D integer array A.

Return a single integer that is the maximum non-empty submatrix sum of this matrix.

Input 1:
    -5 -4 -3
A = -1  2  3
     2  2  4

Input 2:
    1 2 3
A = 4 5 6
    7 8 9

Output 1:
12

Output 2:
45

Explanation 1:
The submatrix with max sum is 
-1 2 3
 2 2 4
 Sum is 12.

Explanation 2:
The largest submatrix with max sum is 
1 2 3
4 5 6
7 8 9
The sum is 45.

public class MaximumSubmatrixSum {
    public int maximumSubmatrixSum(int[][] A) {
        int rows = A.length;
        int cols = A[0].length;
        int maxSum = Integer.MIN_VALUE;
 
        for (int left = 0; left < cols; left++) {
            int[] temp = new int[rows];
            for (int right = left; right < cols; right++) {
                for (int i = 0; i < rows; i++) {
                    temp[i] += A[i][right];
                }
 
                int currSum = 0, maxCurr = Integer.MIN_VALUE;
                for (int val : temp) {
                    currSum = Math.max(val, currSum + val);
                    maxCurr = Math.max(maxCurr, currSum);
                }
 
                maxSum = Math.max(maxSum, maxCurr);
            }
        }
 
        return maxSum;
    }
}

def maximumSubmatrixSum(A):
    rows, cols = len(A), len(A[0])
    max_sum = float('-inf')
 
    for left in range(cols):
        temp = [0] * rows
        for right in range(left, cols):
            for i in range(rows):
                temp[i] += A[i][right]
 
            curr_sum, max_curr = 0, float('-inf')
            for val in temp:
                curr_sum = max(val, curr_sum + val)
                max_curr = max(max_curr, curr_sum)
 
            max_sum = max(max_sum, max_curr)
 
    return max_sum

function maximumSubmatrixSum(A) {
    const rows = A.length;
    const cols = A[0].length;
    let maxSum = Number.NEGATIVE_INFINITY;
 
    for (let left = 0; left < cols; left++) {
        const temp = new Array(rows).fill(0);
        for (let right = left; right < cols; right++) {
            for (let i = 0; i < rows; i++) {
                temp[i] += A[i][right];
            }
 
            let currSum = 0;
            let maxCurr = Number.NEGATIVE_INFINITY;
            for (const val of temp) {
                currSum = Math.max(val, currSum + val);
                maxCurr = Math.max(maxCurr, currSum);
            }
 
            maxSum = Math.max(maxSum, maxCurr);
        }
    }
 
    return maxSum;
}