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 you have read our privacy policy.

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