Question 1 #Link

Question 2 :

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.

For example:

  [ 1 , 4 ]
  [ 2 , 3 ]

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

Your task is to find the maximum sum of two squares of the chessboards on which the rooks can be placed. In the example above, the answer is 6.

Write a function:
solution(A) : which, given a matrix A, returns the maximum sum that can be achieved by placing two nonattacking rooks.

Example 1:

Input: A = [[15, 1, 5],
            [16, 3, 8],
	        [ 2, 6, 4]]
Output: 23

Explanation:  (15 + 8)

Example 2:

Input: A = [[12,12],
	        [12,12],
	        [0, 7]] 
Output: 24  (12 + 12)

Example 3:

Input: A =  [[1,2,14],
             [8,3,15]]
Output: 22 (14 + 8)

Write an efficient algorithm for the following assumptions:
• N and M are an integer within the range [2...600].
• Each element of matrix A is an integer within the range [0...1,000,000,000].