Максимальная подматрица (2D) при игнорировании не более одного элемента
Я знаю, что алгоритм поиска максимальной 2D подматрицы O(m^2*n) с использованием алгоритма Кадане, где m - столбцы, а n - строки. Но существует ли алгоритм для нахождения максимальной 2D подматрицы, если мы должны игнорировать ровно 1 элемент во всей матрице (т.е. мы изменили бы его значение на 0, а затем получили бы максимальную подматрицу)?
Мне бы хотелось, чтобы сложность времени была не намного выше, но я не могу найти эффективный способ сделать это. Кажется, что трудность состоит в том, чтобы знать, какой элемент игнорировать, не пробуя все элементы 1 на 1, а затем каждый раз вычисляя максимальную подматрицу, которая, как я полагаю, будет O(m^3*n^2). Я даже не уверен, возможно ли это, но я чувствую, что может быть способ.
Редактировать: я видел эту статью для решения O(n) с 1-мерным массивом, но я думаю, что обобщение его для массивов более высокой размерности не так просто. Это может быть действительный намек, хотя.