New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Maximum Points

Contributed by

Vishal R S

Easy

0/40

Avg time to solve 10 mins

Success Rate 90 %

8 upvotes

Problem Statement

You are playing a video game, which contains an N x N grid. You start on the top left cell of the grid, and are free to move anywhere through the grid, any number of times.

Each cell in the grid has some number of points that you can collect from it and you can collect points at most once from each cell. Furthermore, it is possible to collect points from a cell, if and only if the cell lies on one of the two diagonals of the grid. Print the maximum number of points you can collect, given the grid.

For example:

If the grid is:
1 2
3 4
We can collect points from all cells as each cell lies on a diagonal. So, the maximum points will be 1+2+3+4 = 10.

Detailed explanation ( Input/output format, Notes, Constraints, Images )

Input Format:

The first line contains 'T', denoting the number of test cases.
For each Test :
The first line contains an integer ‘N’.
The next ‘N’ lines contain ‘N’ space separated integers each, representing the grid.

Output Format:

Print one integer, the maximum number of points you can gain from the grid.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints -

1 <= 'T' <= 10
1 <= ‘N’ <= 1000.
1 <= ‘A[i][j]’ <= 1000, i ∈ [1,N], j ∈ [1,N]
Note: It is guaranteed that the sum of N^2 across all test cases will be at most 10^6.
Time Limit: 1 sec

Sample Input 1:

Sample Output 1

25
5

Explanation for Sample Input 1:

For test case 1:
    We can sum up all the elements that lie on the diagonals, namely 1+5+9+3+7 = 25.

For Test case 2:
    Since there is only one element, we can take it.

Sample Input 2:

Sample Output 2:

Auto

Console