<p>You are given a <code>m x n</code> 2D array <code>board</code> representing a chessboard, where <code>board[i][j]</code> represents the <strong>value</strong> of the cell <code>(i, j)</code>.</p>

<p>Rooks in the <strong>same</strong> row or column <strong>attack</strong> each other. You need to place <em>three</em> rooks on the chessboard such that the rooks <strong>do not</strong> <strong>attack</strong> each other.</p>

<p>Return the <strong>maximum</strong> sum of the cell <strong>values</strong> on which the rooks are placed.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = </span>[[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]</p>

<p><strong>Output:</strong> 4</p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/08/08/rooks2.png" style="width: 294px; height: 450px;" /></p>

<p>We can place the rooks in the cells <code>(0, 2)</code>, <code>(1, 3)</code>, and <code>(2, 1)</code> for a sum of <code>1 + 1 + 2 = 4</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = [[1,2,3],[4,5,6],[7,8,9]]</span></p>

<p><strong>Output:</strong> <span class="example-io">15</span></p>

<p><strong>Explanation:</strong></p>

<p>We can place the rooks in the cells <code>(0, 0)</code>, <code>(1, 1)</code>, and <code>(2, 2)</code> for a sum of <code>1 + 5 + 9 = 15</code>.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = [[1,1,1],[1,1,1],[1,1,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>We can place the rooks in the cells <code>(0, 2)</code>, <code>(1, 1)</code>, and <code>(2, 0)</code> for a sum of <code>1 + 1 + 1 = 3</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= m == board.length &lt;= 100</code></li>
	<li><code>3 &lt;= n == board[i].length &lt;= 100</code></li>
	<li><code>-10<sup>9</sup> &lt;= board[i][j] &lt;= 10<sup>9</sup></code></li>
</ul>

# R3[i]: Three Rooks max value for the first i rows
# R3[0] = R3[1] = R3[2] = -inf
# B = board
# for all i>=3, R3[i] = max(R3[i-1], max_{0<=j<n}(B[i-1, j] + max(R2L[i-1, j], R2R[i-1, n-1-j], C[i-1, j])))
# R2L[i, j]: Two Rooks max value for the first i rows and the left j columns.
# R2R[i, j]: Two Rooks max value for the first i rows and the right j columns.
# C[i, j]: Max value of placing one rook in the top-left i*j region and another rook in the top-right i*(n-1-j) region (i.e. B[0:i, j+1:n]).
# for all j, R2L[0, j] = R2L[1, j] = -inf
# for all i, R2L[i, 0] = R2L[i, 1] = -inf
# for all i>=2 and all j>=2, R2L[i, j] = max(R2L[i-1, j], max_{0<=k<j}(B[i-1, k] + max(M[i-1, 0, k], M[i-1, k+1, j])))
# M[i, j, k]: The max cell value in B[0:i, j:k].
# Similarly for R2R:
# for all j, R2R[0, j] = R2R[1, j] = -inf
# for all i, R2R[i, 0] = R2R[i, 1] = -inf
# for all i>=2 and j>=2, R2R[i, j] = max(R2R[i-1, j], max_{0<k<=j}(B[i-1, -k] + max(M[i-1, n-j, n-k], M[i-1, n-k+1, n])))
# for all j, C[0, j] = C[1, j] = -inf
# for all i, C[i, 0] = C[i, n-1] = -inf
# for all i>=2 and 0<j<n-1, C[i, j] = max(C[i-1, j], ML[i-1, j] + M[i-1, j+1, n], MR[i-1, n-1-j] + M[i-1, 0, j])
# ML[i, j]: The max cell value in B[i, 0:j].
# MR[i, j]: The max cell value in B[i, n-j:n]
# for all j and k, M[0, j, k] = -inf
# for all i and j, M[i, j, j] = - inf
# for all 0 < i, j, and j < k, M[i, j, k] = max(M[i-1, j, k], M[i, j, k-1], B[i-1, k-1])
# for all i, ML[i, 0] = -inf
# for all i and 0<j, ML[i, j] = max(ML[i, j-1], B[i, j-1])
# forall i, MR[i, 0] = -inf
# forall i and 0<j, MR[i, j] = max(MR[i, j-1], B[i, -j])

import numpy as np

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        neg_inf = np.iinfo(np.int64).min
        B = np.array(board, dtype=np.int64)
        m = B.shape[0]
        n = B.shape[1]

        ML = np.zeros([m, n + 1], dtype=np.int64)
        for i in range(m):
            ML[i, 0] = neg_inf
            for j in range(1, n + 1):
                ML[i, j] = max(ML[i, j - 1], B[i, j - 1])

        MR = np.zeros([m, n + 1], dtype=np.int64)
        for i in range(m):
            MR[i, 0] = neg_inf
            for j in range(1, n + 1):
                MR[i, j] = max(MR[i, j - 1], B[i, -j])

        M = np.zeros([m + 1, n + 1, n + 1], dtype=np.int64)
        for j in range(n + 1):
            for k in range(n + 1):
                M[0, j, k] = neg_inf
        for i in range(m + 1):
            for j in range(n + 1):
                M[i, j, j] = neg_inf
        for i in range(1, m + 1):
            for j in range(n + 1):
                for k in range(j + 1, n + 1):
                    M[i, j, k] = max(M[i - 1, j, k], M[i, j, k - 1], B[i - 1, k - 1])

        C = np.zeros([m + 1, n], dtype=np.int64)
        for i in range(2):
            for j in range(n):
                C[i, j] = neg_inf
        for i in range(m + 1):
            for j in (0, n - 1):
                C[i, j] = neg_inf
        for i in range(2, m + 1):
            for j in range(1, n - 1):
                C[i, j] = max(C[i - 1, j], ML[i - 1, j] + M[i - 1, j + 1, n], MR[i - 1, n - 1 - j] + M[i - 1, 0, j])

        R2L = np.zeros([m + 1, n + 1], dtype=np.int64)
        for i in range(2):
            for j in range(n + 1):
                R2L[i, j] = neg_inf
        for i in range(m + 1):
            for j in range(2):
                R2L[i, j] = neg_inf
        for i in range(2, m + 1):
            for j in range(2, n + 1):
                cur_max = R2L[i - 1, j]
                for k in range(j):
                    v = B[i - 1, k] + max(M[i - 1, 0, k], M[i - 1, k + 1, j])
                    if v > cur_max:
                        cur_max = v
                R2L[i, j] = cur_max

        R2R = np.zeros([m + 1, n + 1], dtype=np.int64)
        for i in range(2):
            for j in range(n + 1):
                R2R[i, j] = neg_inf
        for i in range(m + 1):
            for j in range(2):
                R2R[i, j] = neg_inf        
        for i in range(2, m + 1):
            for j in range(2, n + 1):
                cur_max = R2R[i - 1, j]
                for k in range(1, j+1):
                    v = B[i - 1, -k] + max(M[i - 1, n - j, n - k], M[i - 1, n - k + 1, n])
                    if v > cur_max:
                        cur_max = v
                R2R[i, j] = cur_max

        R3 = np.zeros([m + 1], dtype=np.int64)
        for i in range(3):
            R3[i] = neg_inf
        for i in range(3, m + 1):
            cur_max = R3[i - 1]
            for j in range(n):
                v = B[i - 1, j] + max(R2L[i - 1, j], R2R[i - 1, n - 1 - j], C[i - 1, j])
                if v > cur_max:
                    cur_max = v
            R3[i] = cur_max
        return R3[m]


43005