FastPrepFastPrep
Problem Brief

Maximum Sum of Two Non-Attacking Rooks

NEW GRADOA

You are given a matrix A representing a chessboard with N rows and M columns. Each square of the chessboard contains an integer representing a points-based score. You have to place two rooks on the chessboard in such a way that they cannot attack each other and the sum of points on their squares is maximal. Rooks in chess can attack each other only if they are in the same row or column.

Your task is to find the maximum sum of two squares of the chessboards on which the rooks can be placed. We cannot, for example, place the rooks at A[0][1] and A[1][1] (whose sum is 7), as they would attack each other.

Function Description

Write a function:

class Solution { public int solution(int[][] A); }

which, given a matrix A, returns the maximum sum that can be achieved by placing two non-attacking rooks.

1Example 1

Input
A = [[0, 1], [1, 4], [1, 2, 3]]
Output
6
Explanation

We can place rooks in two different ways:

  • One rook on A[0][0] = 1 and another rook on A[1][1] = 3. The sum of points on these squares is 4.
  • One rook on A[0][1] = 4 and another rook on A[1][0] = 2. The sum of points on these squares is 6.

In the example above, the answer is 6. 

public int maxSumOfTwoRooks(int[][] A) {
  // write your code here
}
Input

A

[[0, 1], [1, 4], [1, 2, 3]]

Output

6

Sign in to submit your solution.