Dada una array n*m , la tarea es encontrar la suma máxima de elementos de celdas desde la celda (0, 0) hasta la celda (n-1, m-1).
Sin embargo, los movimientos permitidos son hacia la derecha, hacia abajo o en diagonal hacia la derecha, es decir, desde la ubicación (i, j), el siguiente movimiento puede ser (i+1, j) , o (i, j+1) , o (i+1, j+1) . Encuentre la suma máxima de elementos que satisfacen los movimientos permitidos.
Ejemplos:
Input:
mat[][] = {{100, -350, -200},
{-100, -300, 700}}
Output: 500
Explanation:
Path followed is 100 -> -300 -> 700
Input:
mat[][] = {{500, 100, 230},
{1000, 300, 100},
{200, 1000, 200}}
Explanation:
Path followed is 500 -> 1000 -> 300 -> 1000 -> 200
Enfoque ingenuo: recursividad
Pasar por el enfoque Naive recorriendo todos los caminos posibles. Pero, esto es costoso. Por lo tanto, use Programación Dinámica aquí para reducir la complejidad del tiempo.
C++
#include <bits/stdc++.h>
using namespace std;
#define N 100
// No of rows and columns
int n, m;
// Declaring the matrix of maximum
// 100 rows and 100 columns
int a[N][N];
// For storing current sum
int current_sum = 0;
// For continuous update of
// maximum sum required
int total_sum = 0;
// Function to Input the matrix of size n*m
void inputMatrix()
{
n = 3;
m = 3;
a[0][0] = 500;
a[0][1] = 100;
a[0][2] = 230;
a[1][0] = 1000;
a[1][1] = 300;
a[1][2] = 100;
a[2][0] = 200;
a[2][1] = 1000;
a[2][2] = 200;
}
// Function to calculate maximum sum of path
int maximum_sum_path(int i, int j)
{
// Checking boundary condition
if (i == n - 1 && j == m - 1)
return a[i][j];
// Checking whether the position hasn't
// visited the last row or the last column.
// Making recursive call for all the possible
// moves from the current cell and then adding the
// maximum returned by the calls and updating it.
if (i < n - 1 & j < m - 1) {
int current_sum = max(maximum_sum_path(i, j + 1),
max(
maximum_sum_path(i + 1, j + 1),
maximum_sum_path(i + 1, j)));
total_sum = a[i][j] + current_sum;
}
// Checking whether
// position has reached last row
else if (i == n - 1)
total_sum = a[i][j]
+ maximum_sum_path(i, j + 1);
// If the position is in the last column
else
total_sum = a[i][j]
+ maximum_sum_path(i + 1, j);
// Returning the updated maximum value
return total_sum;
}
// Driver Code
int main()
{
inputMatrix();
// Calling the implemented function
int maximum_sum = maximum_sum_path(0, 0);
cout << maximum_sum;
return 0;
}
Javascript
<script>
const N = 100
// No of rows and columns
let n, m;
// Declaring the matrix of maximum
// 100 rows and 100 columns
let a = new Array(N);
for(let i=0;i<N;i++){
a[i] = new Array(N);
}
// For storing current sum
let current_sum = 0;
// For continuous update of
// maximum sum required
let total_sum = 0;
// Function to Input the matrix of size n*m
function inputMatrix()
{
n = 3;
m = 3;
a[0][0] = 500;
a[0][1] = 100;
a[0][2] = 230;
a[1][0] = 1000;
a[1][1] = 300;
a[1][2] = 100;
a[2][0] = 200;
a[2][1] = 1000;
a[2][2] = 200;
}
// Function to calculate maximum sum of path
function maximum_sum_path(i, j)
{
// Checking boundary condition
if (i == n - 1 && j == m - 1)
return a[i][j];
// Checking whether the position hasn't
// visited the last row or the last column.
// Making recursive call for all the possible
// moves from the current cell and then adding the
// maximum returned by the calls and updating it.
if (i < n - 1 & j < m - 1) {
let current_sum = Math.max(maximum_sum_path(i, j + 1),
Math.max(
maximum_sum_path(i + 1, j + 1),
maximum_sum_path(i + 1, j)));
total_sum = a[i][j] + current_sum;
}
// Checking whether
// position has reached last row
else if (i == n - 1)
total_sum = a[i][j]
+ maximum_sum_path(i, j + 1);
// If the position is in the last column
else
total_sum = a[i][j]
+ maximum_sum_path(i + 1, j);
// Returning the updated maximum value
return total_sum;
}
// Driver Code
inputMatrix();
// Calling the implemented function
let maximum_sum = maximum_sum_path(0, 0);
document.write(maximum_sum,"</br>");
// This code is contributed by shinjanpatra
</script>
Java
// Java program for
// Recursive implementation of
// Max sum path
import java.io.*;
class GFG {
// Function for finding maximum sum
public static int maxPathSum(int matrix[][], int i, int j)
{
if (i<0 || j<0) {
return -100_000_000;
}
if (i==0 && j==0) {
return matrix[i][j];
}
int up = matrix[i][j] + maxPathSum(matrix, i - 1, j);
int right = matrix[i][j] + maxPathSum(matrix, i, j - 1);
int up_left_diagonal = matrix[i][j] + maxPathSum(matrix, i - 1, j - 1);
return Math.max(up , Math.max( right, up_left_diagonal));
}
/* Driver program to test above functions */
public static void main(String[] args)
{
int matrix [][] ={{100, -350, -200}, {-100, -300, 700}};
System.out.print(maxPathSum(matrix, 1, 2));
}
}
// This code is contributed by Rohini Chandra
Producción
3000
Complejidad del tiempo: O(2 N*M )
Espacio auxiliar: O(N*M)
2. Enfoque eficiente (memoización) : la programación dinámica se utiliza para resolver el problema anterior de forma recursiva.
- Asigne una posición al comienzo de la array en (0, 0).
- Verifique cada siguiente posición permitida desde la posición actual y seleccione la ruta con la suma máxima.
- Tenga cuidado con los límites de la array, es decir, si la posición alcanza la última fila o la última columna, la única opción posible será hacia la derecha o hacia abajo, respectivamente.
- Use un mapa para almacenar el seguimiento de todas las posiciones de visita y antes de visitar cualquiera (i, j), verifique si la posición se visitó antes o no.
- Actualice el máximo de todas las rutas posibles devueltas por cada llamada recursiva realizada.
- Vaya hasta que la posición llegue a la celda de destino, es decir, (n-1.m-1).
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
#define N 100
// No of rows and columns
int n, m;
// Declaring the matrix of maximum
// 100 rows and 100 columns
int a[N][N];
// Variable visited is used to keep
// track of all the visited positions
// Variable dp is used to store
// maximum sum till current position
vector<vector<int> > dp(N, vector<int>(N)),
visited(N, vector<int>(N));
// For storing current sum
int current_sum = 0;
// For continuous update of
// maximum sum required
int total_sum = 0;
// Function to Input the matrix of size n*m
void inputMatrix()
{
n = 3;
m = 3;
a[0][0] = 500;
a[0][1] = 100;
a[0][2] = 230;
a[1][0] = 1000;
a[1][1] = 300;
a[1][2] = 100;
a[2][0] = 200;
a[2][1] = 1000;
a[2][2] = 200;
}
// Function to calculate maximum sum of path
int maximum_sum_path(int i, int j)
{
// Checking boundary condition
if (i == n - 1 && j == m - 1)
return a[i][j];
// Checking whether or not (i, j) is visited
if (visited[i][j])
return dp[i][j];
// Marking (i, j) is visited
visited[i][j] = 1;
// Updating the maximum sum till
// the current position in the dp
int& total_sum = dp[i][j];
// Checking whether the position hasn't
// visited the last row or the last column.
// Making recursive call for all the possible
// moves from the current cell and then adding the
// maximum returned by the calls and updating it.
if (i < n - 1 & j < m - 1) {
int current_sum = max(maximum_sum_path(i, j + 1),
max(
maximum_sum_path(i + 1, j + 1),
maximum_sum_path(i + 1, j)));
total_sum = a[i][j] + current_sum;
}
// Checking whether
// position has reached last row
else if (i == n - 1)
total_sum = a[i][j]
+ maximum_sum_path(i, j + 1);
// If the position is in the last column
else
total_sum = a[i][j]
+ maximum_sum_path(i + 1, j);
// Returning the updated maximum value
return dp[i][j] = total_sum;
}
// Driver Code
int main()
{
inputMatrix();
// Calling the implemented function
int maximum_sum = maximum_sum_path(0, 0);
cout << maximum_sum;
return 0;
}
Java
class GFG{
static final int N = 100;
// No of rows and columns
static int n, m;
// Declaring the matrix of maximum
// 100 rows and 100 columns
static int a[][] = new int[N][N];
// Variable visited is used to keep
// track of all the visited positions
// Variable dp is used to store
// maximum sum till current position
static int dp[][] = new int[N][N];
static int visited[][] = new int[N][N];
// For storing current sum
static int current_sum = 0;
// For continuous update of
// maximum sum required
static int total_sum = 0;
// Function to Input the matrix
// of size n*m
static void inputMatrix()
{
n = 3;
m = 3;
a[0][0] = 500;
a[0][1] = 100;
a[0][2] = 230;
a[1][0] = 1000;
a[1][1] = 300;
a[1][2] = 100;
a[2][0] = 200;
a[2][1] = 1000;
a[2][2] = 200;
}
// Function to calculate maximum sum of path
static int maximum_sum_path(int i, int j)
{
// Checking boundary condition
if (i == n - 1 && j == m - 1)
return a[i][j];
// Checking whether or not
// (i, j) is visited
if (visited[i][j] != 0)
return dp[i][j];
// Marking (i, j) is visited
visited[i][j] = 1;
int total_sum = 0;
// Checking whether the position hasn't
// visited the last row or the last column.
// Making recursive call for all the possible
// moves from the current cell and then adding the
// maximum returned by the calls and updating it.
if (i < n - 1 & j < m - 1)
{
int current_sum = Math.max(
maximum_sum_path(i, j + 1),
Math.max(
maximum_sum_path(i + 1, j + 1),
maximum_sum_path(i + 1, j)));
total_sum = a[i][j] + current_sum;
}
// Checking whether position
// has reached last row
else if (i == n - 1)
total_sum = a[i][j] +
maximum_sum_path(i, j + 1);
// If the position is in the last column
else
total_sum = a[i][j] +
maximum_sum_path(i + 1, j);
// Updating the maximum sum till
// the current position in the dp
dp[i][j] = total_sum;
// Returning the updated maximum value
return total_sum;
}
// Driver Code
public static void main(String[] args)
{
inputMatrix();
// Calling the implemented function
int maximum_sum = maximum_sum_path(0, 0);
System.out.println(maximum_sum);
}
}
// This code is contributed by jrishabh99
C#
// C# program to implement
// the above approach
using System;
class GFG{
static readonly int N = 100;
// No of rows and columns
static int n, m;
// Declaring the matrix of maximum
// 100 rows and 100 columns
static int[,]a = new int[N, N];
// Variable visited is used to keep
// track of all the visited positions
// Variable dp is used to store
// maximum sum till current position
static int [,]dp = new int[N, N];
static int [,]visited = new int[N, N];
// For storing current sum
static int current_sum = 0;
// For continuous update of
// maximum sum required
static int total_sum = 0;
// Function to Input the matrix
// of size n*m
static void inputMatrix()
{
n = 3;
m = 3;
a[0, 0] = 500;
a[0, 1] = 100;
a[0, 2] = 230;
a[1, 0] = 1000;
a[1, 1] = 300;
a[1, 2] = 100;
a[2, 0] = 200;
a[2, 1] = 1000;
a[2, 2] = 200;
}
// Function to calculate maximum
// sum of path
static int maximum_sum_path(int i,
int j)
{
// Checking boundary condition
if (i == n - 1 && j == m - 1)
return a[i, j];
// Checking whether or not
// (i, j) is visited
if (visited[i, j] != 0)
return dp[i, j];
// Marking (i, j) is visited
visited[i, j] = 1;
int total_sum = 0;
// Checking whether the position
// hasn't visited the last row
// or the last column.
// Making recursive call for all
// the possible moves from the
// current cell and then adding the
// maximum returned by the calls
// and updating it.
if (i < n - 1 & j < m - 1)
{
int current_sum = Math.Max(maximum_sum_path(i, j + 1),
Math.Max(maximum_sum_path(i + 1,
j + 1),
maximum_sum_path(i + 1, j)));
total_sum = a[i, j] + current_sum;
}
// Checking whether position
// has reached last row
else if (i == n - 1)
total_sum = a[i, j] +
maximum_sum_path(i, j + 1);
// If the position is
// in the last column
else
total_sum = a[i, j] +
maximum_sum_path(i + 1, j);
// Updating the maximum
// sum till the current
// position in the dp
dp[i, j] = total_sum;
// Returning the updated
// maximum value
return total_sum;
}
// Driver Code
public static void Main(String[] args)
{
inputMatrix();
// Calling the implemented function
int maximum_sum = maximum_sum_path(0, 0);
Console.WriteLine(maximum_sum);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement the above approach
let N = 100;
// No of rows and columns
let n, m;
// Declaring the matrix of maximum
// 100 rows and 100 columns
let a = new Array(N);
// Variable visited is used to keep
// track of all the visited positions
// Variable dp is used to store
// maximum sum till current position
let dp = new Array(N);
let visited = new Array(N);
for(let i = 0; i < N; i++)
{
a[i] = new Array(N);
dp[i] = new Array(N);
visited[i] = new Array(N);
for(let j = 0; j < N; j++)
{
a[i][j] = 0;
dp[i][j] = 0;
visited[i][j] = 0;
}
}
// For storing current sum
let current_sum = 0;
// For continuous update of
// maximum sum required
let total_sum = 0;
// Function to Input the matrix
// of size n*m
function inputMatrix()
{
n = 3;
m = 3;
a[0][0] = 500;
a[0][1] = 100;
a[0][2] = 230;
a[1][0] = 1000;
a[1][1] = 300;
a[1][2] = 100;
a[2][0] = 200;
a[2][1] = 1000;
a[2][2] = 200;
}
// Function to calculate maximum sum of path
function maximum_sum_path(i, j)
{
// Checking boundary condition
if (i == n - 1 && j == m - 1)
return a[i][j];
// Checking whether or not
// (i, j) is visited
if (visited[i][j] != 0)
return dp[i][j];
// Marking (i, j) is visited
visited[i][j] = 1;
let total_sum = 0;
// Checking whether the position hasn't
// visited the last row or the last column.
// Making recursive call for all the possible
// moves from the current cell and then adding the
// maximum returned by the calls and updating it.
if (i < n - 1 & j < m - 1)
{
let current_sum = Math.max(
maximum_sum_path(i, j + 1),
Math.max(
maximum_sum_path(i + 1, j + 1),
maximum_sum_path(i + 1, j)));
total_sum = a[i][j] + current_sum;
}
// Checking whether position
// has reached last row
else if (i == n - 1)
total_sum = a[i][j] + maximum_sum_path(i, j + 1);
// If the position is in the last column
else
total_sum = a[i][j] + maximum_sum_path(i + 1, j);
// Updating the maximum sum till
// the current position in the dp
dp[i][j] = total_sum;
// Returning the updated maximum value
return total_sum;
}
inputMatrix();
// Calling the implemented function
let maximum_sum = maximum_sum_path(0, 0);
document.write(maximum_sum);
// This code is contributed by suresh07.
</script>
Python3
N=100 # No of rows and columns n, m=-1,-1 # Declaring the matrix of maximum # 100 rows and 100 columns a=[[-1]*N for _ in range(N)] # Variable visited is used to keep # track of all the visited positions # Variable dp is used to store # maximum sum till current position dp,visited=[[-1]*N for _ in range(N)],[[False]*N for _ in range(N)] # For storing current sum current_sum = 0 # For continuous update of # maximum sum required total_sum = 0 # Function to Input the matrix of size n*m def inputMatrix(): global n, m n = 3 m = 3 a[0][0] = 500 a[0][1] = 100 a[0][2] = 230 a[1][0] = 1000 a[1][1] = 300 a[1][2] = 100 a[2][0] = 200 a[2][1] = 1000 a[2][2] = 200 # Function to calculate maximum sum of path def maximum_sum_path(i, j): global total_sum # Checking boundary condition if (i == n - 1 and j == m - 1): return a[i][j] # Checking whether or not (i, j) is visited if (visited[i][j]): return dp[i][j] # Marking (i, j) is visited visited[i][j] = True # Updating the maximum sum till # the current position in the dp total_sum = dp[i][j] # Checking whether the position hasn't # visited the last row or the last column. # Making recursive call for all the possible # moves from the current cell and then adding the # maximum returned by the calls and updating it. if (i < n - 1 and j < m - 1) : current_sum = max(maximum_sum_path(i, j + 1), max( maximum_sum_path(i + 1, j + 1), maximum_sum_path(i + 1, j))) total_sum = a[i][j] + current_sum # Checking whether # position has reached last row elif (i == n - 1): total_sum = a[i][j] + maximum_sum_path(i, j + 1) # If the position is in the last column else: total_sum = a[i][j] + maximum_sum_path(i + 1, j) # Returning the updated maximum value dp[i][j] = total_sum return total_sum # Driver Code if __name__ == '__main__': inputMatrix() # Calling the implemented function maximum_sum = maximum_sum_path(0, 0) print(maximum_sum)
Producción
3000
Complejidad de tiempo: O(N*M)
Espacio auxiliar: O(N*M) + O(N+M) -> O(NxM) es para la array declarada de tamaño nxm y O(N+M) es para la pila space (llamadas recursivas recursivas máximas).
3. Enfoque de tabulación : este enfoque eliminará la complejidad del espacio extra, es decir, O(N+M) causada por la recursividad en el enfoque anterior.
- Declare una array de tamaño NxM – dp[N][M].
- Recorra la array creada en forma de fila y comience a completar los valores en ella.
- La primera fila de la array `dp`, es decir, el índice (0,j), donde j representa la columna, contendrá los mismos valores que la primera fila de la array `array` dada.
- De lo contrario, calcularemos los valores de arriba (i-1,j), derecha (i,j-1) y arriba_izquierda_diagonal (i-1,j-1) para la celda actual y el valor máximo de ellos será el valor para la celda actual, es decir, dp[i][j].
- Finalmente, la suma máxima de caminos de la array estará en dp[n-1][m-1] donde n=no. de filas y m=no. de columnas
Java
// Java program for
// Recursive implementation of
// Max sum path
import java.io.*;
class GFG {
/* Driver program to test above functions */
public static void main(String[] args)
{
int matrix [][] = {{100, -350, -200}, {-100, -300, 700}};
int n = matrix.length;
int m = matrix[0].length;
int dp[][] = new int [n][m], up, right, up_left_diagonal;
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
if (i==0) {
dp[i][j] = matrix[i][j];
}
else {
up = matrix[i][j];
if(i>0) up += dp[i-1][j];
else up -= (int)Math.pow(10,9);
right = matrix[i][j];
if(j>0) right += dp[i][j-1];
else right -= (int)Math.pow(10,9);
up_left_diagonal = matrix[i][j];
if(i>0 && j>0) up_left_diagonal += dp[i-1][j-1];
else up_left_diagonal -= (int)Math.pow(10,9);
dp[i][j] = Math.max(up , Math.max( right, up_left_diagonal));
}
}
}
System.out.println(dp[n-1][m-1]);
}
}
// This code is contributed by Rohini Chandra
Producción
500
Complejidad del tiempo: O(NxM)
Espacio Auxiliar: O(NxM)