Самая большая прямоугольная подматрица с таким же числом

Ответ 1

Это вопрос, на который я уже ответил здесь (и здесь, измененная версия). В обоих случаях алгоритм применялся к двоичному случаю (нули и единицы), но модификация для произвольных чисел довольно проста (но, к сожалению, Я сохраняю изображения для двоичной версии проблемы). Вы можете сделать это очень эффективно с помощью двухпроцессного алгоритма linear O(n) time - n - количество элементов. Однако это не динамическое программирование - я думаю, что использование динамического программирования здесь было бы неуклюжим и неэффективным, в конце концов, из-за трудностей с проблемой декомпозиции, как упоминалось в OP, если только это не домашнее задание, - но в этом случае вы можете попытаться впечатляют этим алгоритмом:-), поскольку, очевидно, не существует более быстрого решения, чем O(n).

Алгоритм (изображения изображают двоичный случай):

Предположим, вы хотите найти самый большой прямоугольник свободных (белых) элементов.

Здесь следует алгоритм прохождения линейного O(n) времени (n - число элементов):

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

повторите, пока:

Изображения изображают двоичный случай. В случае произвольных чисел вы удерживаете 2 матрицы - сначала с исходными номерами, а вторую с дополнительными номерами, которые заполнены изображением выше. Вы должны проверить исходную матрицу, и если вы найдете число, отличное от предыдущего, вы снова начнете нумерацию (во вспомогательной матрице) с 1.

2) во втором проходе вы переходите по строкам, сохраняя структуру данных потенциальных прямоугольников, т.е. прямоугольники, содержащие текущую позицию где-то на верхнем краю. Смотрите следующее изображение (текущее положение красного цвета, 3 потенциальных прямоугольника - фиолетовый - высота 1, зеленый - высота 2 и желтый - высота 3):

Для каждого прямоугольника мы сохраняем его высоту k и ее левый край. Другими словами, мы отслеживаем суммы последовательных чисел, которые были >= k (т.е. Потенциальные прямоугольники с высотой k). Эта структура данных может быть представлена ​​массивом с двойным связанным списком, связывающим занятые элементы, а размер массива будет ограничен высотой матрицы.

Псевдокод второго прохождения (не двоичная версия с произвольными номерами):

var m[] // original matrix
var aux[] // auxiliary matrix filled in the 1st pass
var rect[] // array of potential rectangles, indexed by their height
           // the occupied items are also linked in double linked list, 
           // ordered by height

foreach row = 1..N // go by rows
    foreach col = 1..M
        if (col > 1 AND m[row, col] != m[row, col - 1]) // new number
            close_potential_rectangles_higher_than(0);  // close all rectangles

        height = aux[row, col] // maximal height possible at current position

        if (!rect[height]) { // rectangle with height does not exist
            create rect[height]    // open new rectangle
            if (rect[height].next) // rectangle with nearest higher height
                                   // if it exists, start from its left edge
                rect[height].left_col = rect[height].next.left_col
            else
                rect[height].left_col = col; 
        }

        close_potential_rectangles_higher_than(height)
    end for // end row
    close_potential_rectangles_higher_than(0);
        // end of row -> close all rect., supposing col is M+1 now!

end for // end matrix

Функция закрытия прямоугольников:

function close_potential_rectangles_higher_than(height)
    close_r = rectangle with highest height (last item in dll)
    while (close_r.height > height) { // higher? close it
        area = close_r.height * (col - close_r.left_col)
        if (area > max_area) { // we have maximal rectangle!
            max_area = area
            max_topleft = [row, close_r.left_col]
            max_bottomright = [row + height - 1, col - 1]
        }
        close_r = close_r.prev
        // remove the rectangle close_r from the double linked list
    }
end function

Таким образом вы также можете получить все максимальные прямоугольники. Итак, в итоге вы получите:

А какая будет сложность? Вы видите, что функция close_potential_rectangles_higher_than составляет O(1) за каждый закрытый прямоугольник. Поскольку для каждого поля мы создаем 1 потенциальный прямоугольник в максимуме, общее количество потенциальных прямоугольников, когда-либо присутствующих в конкретной строке, никогда не превышает длину строки. Поэтому сложность этой функции O(1) амортизирована!

Таким образом, вся сложность O(n), где n - число матричных элементов.

Ответ 2

Динамическое решение:

Определите новую матрицу A, которая будет хранить в A[i,j] два значения: ширину и высоту самой большой подматрицы с левым верхним углом в i,j, заполните эту матрицу, начиная с нижнего правого угла, ряды сверху вниз. Вы найдете четыре случая:

case 1: ни один из элементов правого или нижнего соседа в исходной матрице не равен текущему, т.е. M[i,j] != M[i+1,j] and M[i,j] != M[i,j+1] является M исходной матрицей, в этом случае значение A[i,j] равно 1x1

случай 2: соседний элемент справа равен текущему, а нижний - другому, значение A[i,j].width равно A[i+1,j].width+1 и A[i,j].height=1

случай 3: соседний элемент снизу равен, а правый - другой, A[i,j].width=1, A[i,j].height=A[i,j+1].height+1

случай 4: оба соседства равны: A[i,j].width = min(A[i+1,j].width+1,A[i,j+1].width) и A[i,j].height = min(A[i,j+1]+1,A[i+1,j])

размер самой большой матрицы с верхним левым углом в i,j равен A[i,j].width*A[i,j].height, поэтому вы можете обновить максимальное значение, найденное при расчете A[i,j]

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

в вашем примере, результирующая матрица A будет:

{2:2 1:2 1:1}
{2:1 1:1 1:1}
{1:1 1:1 1:1}

w:h width:height

Ответ 3

Модификация приведенного выше ответа:

Определите новую матрицу A, которая сохранит в [i, j] два значения: ширину и высоту самой большой подматрицы с левым верхним углом в i, j, заполните эту матрицу, начиная с нижнего правого угла, по строкам сверху вниз. Вы найдете четыре случая:

case 1: ни один из элементов правого или нижнего соседа в исходной матрице не равен текущему, т.е. M [i, j]!= M [i + 1, j] и M [i, j]!= M [i, j + 1], являющееся M исходной матрицей, в этом случае значение A [i, j] равно 1x1

случай 2: соседний элемент справа равен текущему, а нижний - другому, значение A [i, j].width равно A [i + 1, j].width + 1 и A [I, J].height = 1

случай 3: соседний элемент снизу равен, но правый - другой, A [i, j].width = 1, A [i, j].height = A [i, j + 1]. высота + 1

случай 4: оба соседства равны:       Рассмотрены три прямоугольника: 1. A [i, j].width = A [i, j + 1].width + 1; A [I, J].height = 1;

• А [I, J].height = А [I + 1, J].height + 1; а [I, J].width = 1;

• A [i, j].width = min (A [i + 1, j].width + 1, A [i, j + 1].width) и A [i, j].height = min (A [i, j + 1] + 1, A [i + 1, j])

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

Размер самой большой матрицы, которая имеет верхний левый угол в i, j, равна A [i, j].width * A [i, j].height, поэтому вы можете обновить максимальное значение, найденное при вычислении A [ I, J]

нижняя строка и самые правые элементы столбца обрабатываются так, как если бы их соседи снизу и справа соответственно были разными.

Ответ 4

Этот вопрос представляет собой дубликат. Я попытался обозначить это как дубликат. Вот решение Python, которое также возвращает положение и форму самой большой прямоугольной подматрицы:

#!/usr/bin/env python3

import numpy

s = '''5 5 8
5 5 7
3 4 1'''

nrows = 3
ncols = 3
skip_not = 5
area_max = (0, [])

a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols)
w = numpy.zeros(dtype=int, shape=a.shape)
h = numpy.zeros(dtype=int, shape=a.shape)
for r in range(nrows):
    for c in range(ncols):
        if not a[r][c] == skip_not:
            continue
        if r == 0:
            h[r][c] = 1
        else:
            h[r][c] = h[r-1][c]+1
        if c == 0:
            w[r][c] = 1
        else:
            w[r][c] = w[r][c-1]+1
        minw = w[r][c]
        for dh in range(h[r][c]):
            minw = min(minw, w[r-dh][c])
            area = (dh+1)*minw
            if area > area_max[0]:
                area_max = (area, [(r, c, dh+1, minw)])

print('area', area_max[0])
for t in area_max[1]:
    print('coord and shape', t)

Вывод:

area 4
coord and shape (1, 1, 2, 2)