Как найти самый большой ряд отрицательных чисел в матрице, который образует прямоугольник

Question

Нужно найти ряд отрицательных чисел, который образует самый большой прямоугольник по площади. Например, у меня есть матрица

 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

Левый верхний угол этого прямоугольника находится на позиции [1][2], а правый нижний угол нах-ся на позиции [3][3]. Какой алгоритм можно составить, чтобы это реализовать?

Answer 1

как вариант можно сделать так:

matrix = [
    [1, -9, -2,  8,   6,  1],
    [ 8, -1, -11, -7,   6,  4],
    [0, 12, -1,  -9, -12, 14],
    [8, 10, -3,  -5,  17,  8],
    [6,  4, 10, -13, -16, 19]
]

def check_matrix(matrix, i0, j0, size_x, size_y):
    for j in range(j0, j0 + size_y):
        for i in range(i0, i0 + size_x):
            if matrix[j][i] >= 0:
                return False

    return True

size_max, data = 0, (-1, -1, 0, 0)

for j in range(len(matrix) - 1):
    for i in range(len(matrix[j]) - 1):
        if matrix[j][i] < 0:
            for size_y in range(1, len(matrix) - j):
                for size_x in range(1, len(matrix[j]) - i):
                    if check_matrix(matrix, i, j, size_x, size_y):
                        if size_max < size_x * size_y:
                            size_max = size_x * size_y
                            data = i, j, size_x, size_y

print(f"i = {data[0]}, j = {data[1]} w = {data[2]} h = {data[3]}")

дальше можно добавлять оптимизации, чтобы свести кол-во анализируемых подматриц к минимуму

в принципе можно обойтись и более коротким извратом, если не нужна скорость, зато без всяких дополнительных функций:

size_max, data = 0, (-1, -1, 0, 0)

for j in range(len(matrix) - 1):
    for i in range(len(matrix[j]) - 1):
        for size_y in range(1, len(matrix) - j):
            for size_x in range(1, len(matrix[j]) - i):
                (size_max, data) = (size_x * size_y, (i, j, size_x, size_y)) if all(all(matrix[y][x] < 0 for x in range(i, i + size_x)) for y in range(j, j + size_y)) and size_max < size_x * size_y else (size_max, data)

БЛОГ НА HUSL

Как найти самый большой ряд отрицательных чисел в матрице, который образует прямоугольник

Ответы (1 шт):