Какова максимальная сумма полей двух неатакующих ладей, поставленных на матрицу? ⇐ JAVA

[Anonymous]

Имеется матрица размером m x n, каждая из которой состоит из целых чисел. Задача состоит в том, что нам нужно разместить в этой матрице две ладьи так, чтобы они не атаковали друг друга, а сумма элементов, на которых расставлены ладьи, была максимальной.
Пример :
Предположим, матрица

Код: Выделить всё

2 5
1 3

Тогда неатакующие ладьи можно ставить только на позиции 2,3 или 1,5 элемента. Но максимальная сумма находится в случае 1,5, поэтому функция должна возвращать 1 + 5 = 6.
Я думал, что мы могли бы пройти по всем парам массива одну за другой. один, а затем возвращаем максимальную сумму, которую мы нашли, но я не могу найти для этого лучшего или эффективного подхода. Мое решение было бы O(m * m * n * n) с точки зрения сложности.
Какой подход будет лучше? Буду признателен за любую помощь.

Подробнее здесь: https://stackoverflow.com/questions/648 ... n-a-matrix