Find a fixed-size submatrix KX×KY with the maximum average value of elements

To find a submatrix of size KX×KY with the maximum average value of elements, prefix sums can be used to speed up the calculation of submatrix sums.

Algorithm:

1. Construct a 2D prefix sum array prefix, where prefix[i][j] is the sum of elements from (0,0) to (i-1,j-1).
2. For each possible submatrix of size KX×KY, calculate the sum in O(1) using prefix sums.
3. Find the submatrix with the maximum sum.

Example code in Python:

def max_avg_submatrix(matrix, KX, KY):
    n, m = len(matrix), len(matrix[0])
    prefix = [[0]*(m+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, m+1):
            prefix[i][j] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

    max_sum = float('-inf')
    max_pos = (0, 0)

    for i in range(n - KX + 1):
        for j in range(m - KY + 1):
            total = prefix[i+KX][j+KY] - prefix[i][j+KY] - prefix[i+KX][j] + prefix[i][j]
            if total > max_sum:
                max_sum = total
                max_pos = (i, j)

    max_avg = max_sum / (KX * KY)
    return max_pos, max_avg

# Example usage
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]
pos, avg = max_avg_submatrix(matrix, 2, 2)
print(f"Maximum average submatrix starts at {pos} with an average value of {avg}")