Given an N x N matrix of integers, compute the maximum sum of any non-empty submatrix. This problem can be efficiently solved by extending the one-dimensional maximum subarray problem (Kadane's algorithm) to two dimensions using prefix sums.

First, precompute a prefix sum array prefixSum where prefixSum[i][j] stores the cumulative sum of elements from the first row to the i-th row in column j. This is calculated as:

prefixSum[i][j] = matrix[i][j] + prefixSum[i-1][j]

with prefixSum[0][j] = 0 for boundary handling.

Next, iterate over all possible pairs of start and end rows (top and bottom). For each pair, compute the column-wise sum between these rows using the prefix sums:

colSum[k] = prefixSum[bottom][k] - prefixSum[top-1][k]

This transforms the submatrix sum problem into a one-dimensional array colSum of length N, where each element represents the sum of a column segment.

Apply Kadane's algorithm to colSum to find the maximum subarray sum, which corresponds to the maximum sum submatrix constrained to the current top and bottom rows. Update the global maximum across all row pairs.

Here is a implementation in C++:

#include <iostream>
#include <climits>
using namespace std;

int main() {
    int N;
    cin >> N;
    int matrix[N+1][N+1];
    int prefixSum[N+1][N+1] = {0};
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> matrix[i][j];
            prefixSum[i][j] = matrix[i][j] + prefixSum[i-1][j];
        }
    }
    
    int maxSum = INT_MIN;
    for (int top = 1; top <= N; top++) {
        for (int bottom = top; bottom <= N; bottom++) {
            int currentSum = 0;
            for (int col = 1; col <= N; col++) {
                int colSegmentSum = prefixSum[bottom][col] - prefixSum[top-1][col];
                currentSum = max(colSegmentSum, currentSum + colSegmentSum);
                maxSum = max(maxSum, currentSum);
            }
        }
    }
    cout << maxSum << endl;
    return 0;
}

The algorithm runs in O(N^3) time due to the triple nested loops over rows and columns, with O(N^2) space for the prefix sum table.