Find the maximum sum path in the given Matrix
Consider an infinite matrix. The cells of the matrix are filled with natural numbers from the cell (1, 1) in the direction of top right to bottom left diagonally. Then the task is to output the Maximum path sum between two points (X1, Y1) and (X2, Y2).
Matrix filling process is as follows:
Examples:
Input: X1 = 1, Y1 = 1, X2 = 3, Y2 = 3
Output: 32
Explanation: The best path for maximum sum for reaching (X2, Y2) from (X1, Y1) will be: 1 → 3 → 6 → 9 →13.Input: X1 = 2, Y1 = 3, X2 = 4, Y2 = 5
Output: 97
Explanation: It can be verified that the maximum sum of the path will be 97.
Approach: Implement the idea below to solve the problem
The problem is observation based and can be solved using the precomputing the values of matrix then traversing in a greedy manner.
Steps were taken to solve the problem:
- Initialize Variables: Create a StringBuilder let say SB for storing output. Also, define a 2D array let say XY[][] for storing the values of each cell in the matrix.
- Precompute Cell Values: In the main() function, precompute the values of each cell in the matrix. The value of each cell is equal to the sum of its coordinates (X, Y). This can be done by iterating over all cells in the matrix and adding their values to XY[i][j].
- Calculate Sum on Path: Calculate the maximum possible sum on a path from (X1, Y1) to (X2, Y2) by moving right and down in the precomputed matrix XY[][]. This can be done by adding up the values in all cells from (X1, Y1) to (X2, Y1), and then from (X2, Y1+1) to (X2, Y2).
- Store Result: Append the calculated sum for each test case to the StringBuilder SB.
- Print All Results: Print all results stored in SB.
Code to implement the approach:
C++
#include <iostream> #include <vector> using namespace std; // Driver class int main() { int N = 2005; // Matrix for storing cell values vector<vector< long long >> xy(N, vector< long long >(N)); long long start = 1LL; // Precompute cell values for ( int i = 0; i < N; i++) { int ti = 0, tj = i; while (ti >= 0 && tj >= 0) xy[ti++][tj--] = start++; } for ( int i = 1; i < N; i++) { int ti = i, tj = N - 1; while (ti < N && tj < N) xy[ti++][tj--] = start++; } // Define input coordinates int x1 = 1, y1 = 1; int x2 = 3, y2 = 3; // Convert coordinates to 0-based indexing x1--; x2--; y1--; y2--; long long s = xy[x2][y2]; // Calculate the sum along the path while (x1 < x2) s += xy[x1++][y1]; while (y1 < y2) s += xy[x2][y1++]; // Print the result cout << s << endl; return 0; } |
Java
// Java code to implement the approach import static java.lang.Math.*; import java.util.*; // Driver class public class Main { // StringBuilder for storing output static StringBuilder sb = new StringBuilder(); // Main Function public static void main(String[] ScoobyDoobyDo) { // Size of the matrix (User defined) int N = 2005 ; // Matrix for storing cell values xy = new long [N][N]; // Precompute cell values long start = 1L; for ( int i = 0 ; i < N; i++) { int ti = 0 , tj = i; while (ti >= 0 && tj >= 0 ) xy[ti++][tj--] = start++; } for ( int i = 1 ; i < N; i++) { int ti = i, tj = N - 1 ; while (ti < N && tj < N) xy[ti++][tj--] = start++; } // Function call solve(); // Print all results System.out.println(sb); } static long [][] xy; public static void solve() { // Inputs int x1 = 1 , y1 = 1 ; int x2 = 3 , y2 = 3 ; // Changing to 0 based indexing x1--; x2--; y1--; y2--; // Calculate sum on path from // (x1, y1) to (x2, y2) long s = xy[x2][y2]; while (x1 < x2) s += xy[x1++][y1]; while (y1 < y2) s += xy[x2][y1++]; // Append result to StringBuilder sb.append(s + "\n"); } } |
Python
# Size of the matrix (User defined) N = 2005 # Matrix for storing cell values xy = [[ 0 ] * N for _ in range (N)] start = 1 # Precompute cell values for i in range (N): ti, tj = 0 , i while ti > = 0 and tj > = 0 : xy[ti][tj] = start start + = 1 ti + = 1 tj - = 1 for i in range ( 1 , N): ti, tj = i, N - 1 while ti < N and tj < N: xy[ti][tj] = start start + = 1 ti + = 1 tj - = 1 # Define input coordinates x1, y1 = 1 , 1 x2, y2 = 3 , 3 # Convert coordinates to 0-based indexing x1 - = 1 x2 - = 1 y1 - = 1 y2 - = 1 s = xy[x2][y2] # Calculate the sum along the path while x1 < x2: s + = xy[x1][y1] x1 + = 1 while y1 < y2: s + = xy[x2][y1] y1 + = 1 # Print the result print (s) |
C#
using System; class Program { // Driver class static void Main( string [] args) { // Size of the matrix (User defined) int N = 2005; // Matrix for storing cell values long [,] xy = new long [N, N]; long start = 1L; // Precompute cell values for ( int i = 0; i < N; i++) { int ti = 0, tj = i; while (ti >= 0 && tj >= 0) xy[ti++, tj--] = start++; } for ( int i = 1; i < N; i++) { int ti = i, tj = N - 1; while (ti < N && tj < N) xy[ti++, tj--] = start++; } //Inputs int x1 = 1, y1 = 1; int x2 = 3, y2 = 3; // Changing to 0 based indexing x1--; x2--; y1--; y2--; // Calculate sum on path from // (x1, y1) to (x2, y2) long s = xy[x2, y2]; while (x1 < x2) s += xy[x1++, y1]; while (y1 < y2) s += xy[x2, y1++]; //Print the results Console.WriteLine(s); } } |
Javascript
// Size of the matrix (User defined) let N = 2005; // Matrix for storing cell values let xy = new Array(N); for (let i = 0; i < N; i++) { xy[i] = new Array(N); } //Precompute the cell's value let start = 1n; for (let i = 0; i < N; i++) { let ti = 0, tj = i; while (ti >= 0 && tj >= 0) { xy[ti++][tj--] = start++; } } for (let i = 1; i < N; i++) { let ti = i, tj = N - 1; while (ti < N && tj < N) { xy[ti++][tj--] = start++; } } //Inputs let x1 = 1, y1 = 1; let x2 = 3, y2 = 3; // Changing to 0 based indexing x1--; x2--; y1--; y2--; // Calculate sum on path from // (x1, y1) to (x2, y2) let s = xy[x2][y2]; while (x1 < x2) { s += xy[x1++][y1]; } while (y1 < y2) { s += xy[x2][y1++]; } //Print the result console.log(s); |
32
Time Complexity: O(N*M), Where N and M are nearly equivalent to X2 and Y2 respectively.
Auxiliary space: O(N*M)