Find maximum sum of all diagonals in matrix Python

In this tutorial, we will learn how we can traverse through all diagonals in a 2D matrix in Python.

Find the maximum sum of all diagonals in matrix Python

This question is based on Google Kickstart Round G Maximum Coins problem on October 18th 2020.

In this problem, our goal is to traverse through all diagonals (not only the primary diagonal) and in turn calculate the sum of each of them. Our bigger goal is to return the maximum of those. In this approach, it is clear that we have to access each element at least once. That makes it clear that our search time is proportional to O(n^2).

Take the array

1 2 5

3 6 1

12 2 7
In this case, we need to be traversing through the following diagonals represented by the elements:

5

2 1

1 6 7

3 2

12

Among these diagonals, we see that the maximum sum is with the principal diagonal. Thus the code should return 14.

0 0 0 0 0

1 1 1 1 0

2 2 2 8 0

1 1 1 0 0

0 0 0 0 0

Accessing all elements in the same way as last time we see that the diagonal with elements 0 1 8 0 returns the largest sum. The solution in this case would be 9.

the above examples are from Google Kickstart. Please visit the problem here at: https://codingcompetitions.withgoogle.com/kickstart/round/00000000001a0069/0000000000414a23

The code below solves all test cases for the problem. At a time we make sure we access one of the diagonals alone. We check the sum if it can be bigger than the previous one. this has been implemented in two phases. The first nested for loop block tests the upper triangular half of the matrix space. The subsequent block tests the

def myfunc(arr):
    mymax=0
    count=0
    for i in range(0, len(arr)):
        sum=0
        
        for j in range(0, len(arr)-i):
            sum+=arr[i+j-count][j+count]
        count+=1
        if(sum>mymax):
            mymax=sum
    count=1
    
    for k in range(1, len(arr)):
        sum=0
        for h in range(0, len(arr)-k):
            sum+=arr[h+count][k+h-count]
        count+=1
        
        if(sum>mymax):
            mymax=sum
    return mymax
        
t=int(input())
for i in range(0, t):
    n=int(input())
    arr=[]
    for j in range(0, n):
        sarr = list(map(int, input().rstrip().split()))
        arr.append(sarr)
  
    result=myfunc(arr)
    print("Case #"+str(i+1)+": "+str(result))
    

Also read: Diagonal traversal of a binary tree in Python