1

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

 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]. Какой алгоритм можно составить, чтобы это реализовать?

3
  • самый большой прямоугольник по площади?
    – Zhihar
    17 ноя 2021 в 17:06
  • Да,, по площади
    – Khimer
    17 ноя 2021 в 17:08
  • 1
    Задача может быть решена за линейное (пропорциональное площади матрицы) время: e-maxx.ru/algo/maximum_zero_submatrix . 17 ноя 2021 в 17:53

1 ответ 1

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)
2
  • спасибо большое, благодаря вашему коду нашел свои ошибки в моем алгоритме
    – Khimer
    17 ноя 2021 в 17:33
  • а что за ошибка, если не секрет? нестрогое равенство использовали?
    – Zhihar
    17 ноя 2021 в 17:37

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.