<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>

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        """
        You need to place 3 rooks 
        n = 100
        
        greedy，取大的會怎樣?
        馬上就想到
        
        10  9  0
        9   3  0
        0   3  3        
        如果從大的開始取，就得到10+3+3 = 16
        但實際答案是9+9+3 = 21
        
        
        暴力法 for x1,y1, x2,y2, x3, y3 = O(10^12)
        我原本想能不能sort，不行
        sort後
        10  9  0
        9   3  0
        3   3  0
        
        brute force: O(10^4)
        """
        def sol1():
            lenX, lenY = len(board[0]), len(board)
            
            ans = -inf
            for x1 in range(lenX):
                for x2 in range(lenX):
                    if x1 == x2: continue
                    for x3 in range(lenX):
                        if x1 == x3 or x2 == x3: continue
            
                        for y1 in range(lenY):
                            for y2 in range(lenY):
                                if y1 == y2: continue
                                for y3 in range(lenY):
                                    if y1 == y3 or y2 == y3: continue
                                    ans = max(ans, board[y1][x1] + board[y2][x2] + board[y3][x3])
            
            return ans
        #return sol1()   # O(n^4) n=100, LTE
        
        """
        lucky greedy
        """
        def sol1_2():
            lenX, lenY = len(board[0]), len(board)

            
            def top3_indices(arr):
                # Get the indices of the top 3 values in descending order
                sorted_indices = sorted(range(len(arr)), key=lambda i: -arr[i])
                top_indices = sorted_indices[:3]
                return top_indices

            def backtrace(y, current_sum, used_x):
                # Base case: If we have selected 3 rows, check the maximum sum
                if len(used_x) == 3:
                    self.ans = max(self.ans, current_sum)
                    return

                # If we've processed all rows, stop recursion
                if y == lenY:
                    return

                # Recurse without selecting the current row
                backtrace(y + 1, current_sum, used_x)

                # Try to add elements from the current row
                for x in top3_indices(board[y]):
                    if x not in used_x:
                        used_x.add(x)
                        backtrace(y+1, current_sum + board[y][x], used_x)
                        used_x.remove(x)

            self.ans = float('-inf')
            used_x = set()
            backtrace(0, 0, used_x)
            return self.ans
        #return sol1_2()    # LTE
        
        """
        https://leetcode.com/problems/maximum-value-sum-by-placing-three-rooks-i/discuss/5651267/Placing-rooks-in-any-3-rows-or-TC%3A-O(3M-*-3M*-3M)-or-Full-explanation
        
        對三個row，最大的三個，做檢查
        TC: O(n^3)
        """
        def sol1_3():
            lenY, lenX = len(board), len(board[0])

            top3_idx_rows = [list() for _ in range(lenY)]
            for y in range(lenY):
                tmp = [(val, j) for j, val in enumerate(board[y])]
                tmp.sort(reverse = True)
                #top3_idx_rows [y] = [j for _, j in tmp]  # LTE
                top3_idx_rows[y] = [tmp[j][1] for j in range(3)]

            ans = -inf
            for y1 in range(lenY):
                for y2 in range(y1+1, lenY):
                    for y3 in range(y2+1, lenY):
                
                        for x1 in top3_idx_rows[y1]:
                            for x2 in top3_idx_rows[y2]:
                                for x3 in top3_idx_rows[y3]:

                                    if x1 != x2 and x2 != x3 and x3 != x1:

                                        tmp = board[y1][x1] + board[y2][x2] + board[y3][x3]
                                        ans = max(ans, tmp)

            return ans
        return sol1_3()
        

        """
        感覺和DP有關
        """
        
        def sol2():
            m, n = len(board), len(board[0])
            numOfBrook = 3
            dp = [[[-inf] * (numOfBrook) for _ in range(n)] for _ in range(m + 1)]
    
            for j in range(n):
                dp[1][j][1] = board[0][j]

            for i in range(2, m + 1):
                for j in range(n):
                    for k in range(numOfBrook): 
                        
                        # 不再這行放車
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k])

                        for prev_j in range(n):
                            if prev_j != j: 
                                dp[i][j][k] = max(dp[i][j][k], dp[i-1][prev_j][k-1] + board[i-1][j])

            return max(dp[m][j][3] for j in range(n))
        #return sol2()
        
        
18435