Написал довольно производительное решение на свёртках. Для вычисления свёртки conv матрицы mask с ядром kernel используется filter2d из OpenCV, но эта функция может быть заменена на аналогичную из любой другой математической библиотеки - надо смотреть, какая быстрее. Также принципиально, что вычисления производятся во float32, а не в целых числах - так на порядки (!) быстрее.
import cv2
import numpy as np
data = """1 -9 -2 8 6 1
8 -1 -11 -7 6 4
10 12 -1 -9 -12 14
8 10 -3 -5 17 8
6 4 10 -13 -16 19"""
# matrix = np.random.randint(-128, 128, (1000, 1000), dtype=np.int32)
matrix = np.int32([line.split() for line in data.splitlines()])
def find_max_kernel(matrix, border=cv2.BORDER_ISOLATED):
max_area = 0
mask = np.float32(matrix < 0)
ones = np.ones_like(mask)
conv_x = np.zeros_like(mask)
conv_y = np.zeros_like(mask)
max_h, max_w = mask.shape
for h in range(1, max_h + 1):
cv2.filter2D(mask, -1, ones[:h, None, 0], conv_y, (0, 0), 0, border)
for w in range(1, max_w + 1):
area = h * w
if area > max_area:
cv2.filter2D(conv_y, -1, ones[None, 0, :w], conv_x, (0, 0), 0, border)
if conv_x.max() == area:
max_area, shape = area, (h, w)
else:
if w == 1:
max_h = h - 1
if h == 1:
max_w = w - 1
break
if h >= max_h:
break
cv2.filter2D(mask, -1, np.ones(shape, np.float32), conv_x, (0, 0), 0, border)
p1 = np.array(np.unravel_index(conv_x.argmax(), conv_x.shape))
p2 = p1 + shape - 1
return p1, p2
print(*find_max_kernel(matrix), sep='\n')
Матрица 1000 х 1000 на моих 2 ядрах обрабатывается в среднем за 82 мс:
Пример применения алгоритма: найдена самая большая субматрица - вписанный квадрат
