Last Updated: 6 Jan, 2022
Maximum Points
Easy
Asked in companies
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.
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
Approaches
Approach:
We iterate over all the elements in the grid and check if the current element is present on at least one of the diagonals or not. If it is on one of the diagonals, we can add it the the answer.
Algorithm:
- Initialize ans=0
- Iterate a loop from i=0 to N-1
- Iterate a loop from j=0 to N-1
- If i==j or i+j==n-1 //Check if it lies on any diagonal
- Assign ans = ans + grid[i][j]
- Iterate a loop from j=0 to N-1
- Return ans
Approach:
We can first iterate over all the elements on the principal diagonal of the grid and add them to the answer variable. Then we can iterate over all the elements in the secondary diagonal and add them to the answer variable.
In cases where ‘N’ is odd, the middle element in the grid (middle row, middle column) is part of both the principal and secondary diagonal and gets added twice. Hence in this case, we must subtract the middle element from the answer variable.
Algorithm:
- Initialize ans = 0
- Iterate a loop from i=0 to N-1
- Assign ans = ans + grid[i][i] // Principal Diagonal
- Assign ans = ans + grid[i][N-1-i] // Secondary Diagonal
- If ‘N’ is odd
- Assign ans = ans - grid[N/2][N/2]
- Return ans