Given a 2D square matrix arr[][] of dimensions N x N, the task is to find the maximum path sum by moving diagonally from any cell and each cell must be visited only once i.e., from the cell (i, j), a player can move to the cell (i + 1, j + 1).
Examples:
Input: arr[][] = {{1, 2, 3}, {3, 5, 10}, {1 3 5}}
Output: 12
Explanation:
Sum of cells (1, 1), (2, 2) and (3, 3) is 11.
The sum of cells (1, 2), (2, 3) and (1, 3) is 3.
The sum of cells (2, 1) and (3, 2) is 6.
The sum of cell (3, 1) is 1.
The maximum possible sum is 12.Input: arr[][] = {{1, 1, 1}, {1 1 1}, {1 1 1}}
Output: 3
Approach: To solve this problem, the idea is to traverse the matrix diagonally for first row and column elements and sum up their diagonal elements within the range of the matrix.
Follow the steps below to solve the problem:
- Initialize a variable, say max with 0.
- Choose each cell (i, j) from the first row and from the first column.
- Now, from each cell, find the diagonal sum starting from that cell by incrementing i and j by 1, say sum.
- Then, update max as max(max, sum).
- After traversing, print max as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sumint MaximumSum(vector<vector<int> >& arr, int n){ int ans = 0; // Loop to traverse through the // upper triangular matrix and // update the maximum sum to ans for (int i = 0; i < n; i++) { int x = 0, y = i, sum = 0; for (int j = i; j < n; j++) { sum += arr[x++][y++]; } if (sum > ans) ans = sum; } // Traverse through the // lower triangular matrix for (int i = 1; i < n; i++) { int x = i, y = 0, sum = 0; for (int j = i; j < n; j++) { sum += arr[x++][y++]; } if (sum > ans) ans = sum; } return ans;}// Driver Codeint main(){ // Given matrix vector<vector<int> > arr; arr = { { 1, 2, 3 }, { 3, 5, 10 }, { 1, 3, 5 } }; // Given dimension int n = arr.size(); cout << MaximumSum(arr, n); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the maximum sumstatic int MaximumSum(int [][]arr, int n){ int ans = 0; // Loop to traverse through the // upper triangular matrix and // update the maximum sum to ans for (int i = 0; i < n; i++) { int x = 0, y = i, sum = 0; for (int j = i; j < n; j++) { sum += arr[x++][y++]; } if (sum > ans) ans = sum; } // Traverse through the // lower triangular matrix for (int i = 1; i < n; i++) { int x = i, y = 0, sum = 0; for (int j = i; j < n; j++) { sum += arr[x++][y++]; } if (sum > ans) ans = sum; } return ans;}// Driver Codepublic static void main(String[] args){ // Given matrix int [][]arr = { { 1, 2, 3 }, { 3, 5, 10 }, { 1, 3, 5 } }; // Given dimension int n = arr.length; System.out.print(MaximumSum(arr, n));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to find the maximum sumdef MaximumSum(arr, n): ans = 0; # Loop to traverse through the # upper triangular matrix and # update the maximum sum to ans for i in range(n): x, y, sum = 0, i, 0 for j in range(i, n): sum, x, y =sum + arr[x][y], x + 1, y + 1 if (sum > ans): ans = sum # Traverse through the # lower triangular matrix for i in range(1, n): x, y, sum = i, 0, 0 for j in range(i, n): sum, x, y =sum + arr[x][y], x + 1, y + 1 if (sum > ans): ans = sum return ans# Driver Codeif __name__ == '__main__': # Given matrix arr = [ [ 1, 2, 3], [ 3, 5, 10], [ 1, 3, 5 ]] # Given dimension n = len(arr) print (MaximumSum(arr, n)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the maximum sum static int MaximumSum(int [,]arr, int n) { int ans = 0; // Loop to traverse through the // upper triangular matrix and // update the maximum sum to ans for (int i = 0; i < n; i++) { int x = 0, y = i, sum = 0; for (int j = i; j < n; j++) { sum += arr[x++, y++]; } if (sum > ans) ans = sum; } // Traverse through the // lower triangular matrix for (int i = 1; i < n; i++) { int x = i, y = 0, sum = 0; for (int j = i; j < n; j++) { sum += arr[x++, y++]; } if (sum > ans) ans = sum; } return ans; } // Driver Code public static void Main(String[] args) { // Given matrix int [,]arr = { { 1, 2, 3 }, { 3, 5, 10 }, { 1, 3, 5 } }; // Given dimension int n = arr.GetLength(0); Console.Write(MaximumSum(arr, n)); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program of the above approach// Function to find the maximum sumfunction MaximumSum(arr, n){ let ans = 0; // Loop to traverse through the // upper triangular matrix and // update the maximum sum to ans for (let i = 0; i < n; i++) { let x = 0, y = i, sum = 0; for (let j = i; j < n; j++) { sum += arr[x++][y++]; } if (sum > ans) ans = sum; } // Traverse through the // lower triangular matrix for (let i = 1; i < n; i++) { let x = i, y = 0, sum = 0; for (let j = i; j < n; j++) { sum += arr[x++][y++]; } if (sum > ans) ans = sum; } return ans;} // Driver Code // Given matrix let arr = [[ 1, 2, 3 ], [ 3, 5, 10 ], [ 1, 3, 5 ]]; // Given dimension let n = arr.length; document.write(MaximumSum(arr, n)); </script> |
Output
12
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
