Maximum Points

Easy

0/40

Average time to solve is 10m

Contributed by

10 upvotes

Asked in companies

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, 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:

Hint 1

Hint 2

Can we iterate over all cells and check if we can gain points from it?

Approaches (2)

Approach 1

Approach 2

Brute Force

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]
Return ans

Time Complexity

O(N^2), where ‘N’ is the length of the grid.

We iterate over all the elements in the grid, and since the NxN grid has N^2 cells, the time complexity is O(N^2).

Space Complexity

O(1), as we use a constant amount of additional space.

(100% EXP penalty)

Maximum Points

Console