Дана доска M×N, в каждой клетке записано целое число (возможно, отрицательное).
Ладью ставят на одну клетку; она бьёт всю свою строку и весь свой столбец.
Нужно поставить ладью так, чтобы сумма чисел на побитых клетках (включая клетку,
где она стоит, — один раз) была максимальной, и вернуть эту сумму.
// RookMaxSum возвращает максимальную сумму клеток под боем ладьи.
func RookMaxSum(board [][]int) int
Примеры
[[2,3,4],
[4,5,2],
[4,6,3]] → 21 (ладья на 6: строка 4+6+3 и столбец 3+5, итого 21)
[[2,3,4,5]] → 14 (одна строка — ладья бьёт её целиком)
[[-1,-2],
[-3,-4]] → -6
Ограничения
1 ≤ M, N, M·N ≤ 4·10⁶, доска прямоугольная, |board[i][j]| ≤ 10⁹.- Доску менять нельзя.
- Ожидается O(M·N). Пересчёт строки и столбца для каждой клетки — O(M·N·(M+N)) —
на большой доске не проходит по времени.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.