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:
1 6 7
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))
Leave a Reply