Problem statement

https://binarysearch.com/problems/Maximize-Rook-Square-Values/

Solution 1

If we choose cell, all board will be divided into 4 parts. We need to find maximums on each of this parts. We can use dp to do it.

Complexity

It is O(mn) for time and space, but constant is quite big, so in python it gives TLE.

Code

class Solution:
    def solve(self, A):
        n, m = len(A), len(A[0])

        @lru_cache(None)
        def dp(i, j, d1, d2):
            if not 0 <= i < n or not 0 <= j < m: return -float("inf")
            return max(dp(i+d1, j, d1, d2), dp(i, j+d2, d1, d2), A[i][j])

        ans = 0
        for i in range(n):
            for j in range(m):
                for d1 in [-1, 1]:
                    for d2 in [-1, 1]:
                        ans = max(ans, A[i][j] + dp(i+d1, j+d2, d1, d2))

        return ans

Solution 2

Let (row, col) be the cell with maximum value. Then we can have 2 options:

  1. We choose this cell and another such that they do not beat each other.
  2. We choose one cell on the row and one cell on the column with this cell.

Complexity

It is still O(mn) for time and space, but several times faster.

Code

class Solution:
    def solve(self, A):
        n, m = len(A), len(A[0])
        maxval, row, col = max((A[r][c], r, c) for r in range(n) for c in range(m))
        maxcol = max(A[r][col] for r in range(n) if r != row)
        maxrow = max(A[row][c] for c in range(m) if c != col)
        maxother = max(A[r][c] for r in range(n) for c in range(m) if r != row and c != col)
        return max(maxval + maxother, maxrow + maxcol)