Какова максимальная сумма полей двух неатакующих ладей, поставленных на матрицу? ⇐ 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