Найти подматрицу фиксированного размера KX×KY с максимальным средним значением элементов

Для поиска подматрицы размера KX×KY с максимальным средним значением элементов можно использовать префиксные суммы для ускорения вычислений суммы элементов подматриц.

Алгоритм:

1. Построить двумерный массив префиксных сумм prefix, где prefix[i][j] — сумма элементов от (0,0) до (i-1,j-1).
2. Для каждой возможной подматрицы размера KX×KY вычислить сумму за O(1) с помощью префиксных сумм.
3. Найти подматрицу с максимальной суммой.

Пример кода на 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

# Пример использования
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"Максимальная средняя подматрица начинается в {pos} со средним значением {avg}")