How should I practice Maximum Sum of Two Non-Attacking Rooks?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Maximum Sum of Two Non-Attacking Rooks associated with Microsoft?

FastPrep tags this as a Microsoft coding interview or online assessment practice problem when the problem catalog has that company context.

FastPrep

Problem · Matrix

Maximum Sum of Two Non-Attacking Rooks

● MediumMicrosoftNEW GRADOA

See Microsoft hiring insights

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.

Examples

01 · Example 1

A = [[0, 1], [1, 4], [1, 2, 3]]
return = 6

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.