Ruta de suma máxima en una array de arriba a abajo y viceversa

Posted on by Rudeus Greyrat

Dada una array de dimensión N * M . La tarea es encontrar la suma máxima de la ruta desde arr[0][0] a arr[N – 1][M – 1] y viceversa desde arr[N – 1][M – 1] a arr[0][0 ] . 
En el camino de arr[0][0] a arr[N – 1][M – 1] , puede atravesar hacia abajo y hacia la derecha y en el camino de arr[N – 1][M – 1] a arr [0][0] , puede desplazarse hacia arriba y hacia la izquierda. 
Nota : ambas rutas no deben ser iguales, es decir, debe haber al menos una celda arr[i][j] que no sea común en ambas rutas.
Ejemplos: 
 

Input: 
mat[][]= {{1, 0, 3, -1},
          {3, 5, 1, -2},
          {-2, 0, 1, 1},
          {2, 1, -1, 1}}
Output: 16

Maximum sum on path from arr[0][0] to arr[3][3] 
= 1 + 3 + 5 + 1 + 1 + 1 + 1 = 13
Maximum sum on path from arr[3][3] to arr[0][0] = 3
Total path sum = 13 + 3 = 16

Input: 
mat[][]= {{1, 0},
          {1, 1}}
Output: 3

Enfoque: este problema es algo similar al problema de la ruta de costo mínimo , excepto que en el presente problema se deben encontrar dos rutas con suma máxima. Además, debemos tener cuidado de que las celdas en ambos caminos contribuyan solo una vez a la suma. 
Lo primero que hay que notar es que la ruta de arr[N – 1][M – 1] a arr[0][0] no es más que otra ruta de arr[0][0] a arr[N – 1][M – 1] . Entonces, tenemos que encontrar dos caminos desde arr[0][0] hasta arr[N – 1][M – 1] con suma máxima. 
Abordando de manera similar al problema de la ruta de costo mínimo, comenzamos ambas rutas desde arr[0][0]juntos y recurrimos a las celdas vecinas de la array hasta llegar a arr[N – 1][M – 1] . Para asegurarnos de que una celda no contribuya más de una vez, verificamos si la celda actual en ambas rutas es la misma o no. Si son iguales, se agrega a la respuesta solo una vez.
A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Input matrix
int n = 4, m = 4;
int arr[4][4] = { { 1, 0, 3, -1 },
                  { 3, 5, 1, -2 },
                  { -2, 0, 1, 1 },
                  { 2, 1, -1, 1 } };
 
// DP matrix
int cache[5][5][5];
 
// Function to return the sum of the cells
// arr[i1][j1] and arr[i2][j2]
int sum(int i1, int j1, int i2, int j2)
{
    if (i1 == i2 && j1 == j2) {
        return arr[i1][j1];
    }
    return arr[i1][j1] + arr[i2][j2];
}
 
// Recursive function to return the
// required maximum cost path
int maxSumPath(int i1, int j1, int i2)
{
 
    // Column number of second path
    int j2 = i1 + j1 - i2;
 
    // Base Case
    if (i1 >= n || i2 >= n || j1 >= m || j2 >= m) {
        return 0;
    }
 
    // If already calculated, return from DP matrix
    if (cache[i1][j1][i2] != -1) {
        return cache[i1][j1][i2];
    }
    int ans = INT_MIN;
 
    // Recurring for neighbouring cells of both paths together
    ans = max(ans, maxSumPath(i1 + 1, j1, i2 + 1) + sum(i1, j1, i2, j2));
    ans = max(ans, maxSumPath(i1, j1 + 1, i2) + sum(i1, j1, i2, j2));
    ans = max(ans, maxSumPath(i1, j1 + 1, i2 + 1) + sum(i1, j1, i2, j2));
    ans = max(ans, maxSumPath(i1 + 1, j1, i2) + sum(i1, j1, i2, j2));
 
    // Saving result to the DP matrix for current state
    cache[i1][j1][i2] = ans;
 
    return ans;
}
 
// Driver code
int main()
{
    memset(cache, -1, sizeof(cache));
    cout << maxSumPath(0, 0, 0);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
// Input matrix
static int n = 4, m = 4;
static int arr[][] = { { 1, 0, 3, -1 },
                { 3, 5, 1, -2 },
                { -2, 0, 1, 1 },
                { 2, 1, -1, 1 } };
 
// DP matrix
static int cache[][][] = new int[5][5][5];
 
// Function to return the sum of the cells
// arr[i1][j1] and arr[i2][j2]
static int sum(int i1, int j1, int i2, int j2)
{
    if (i1 == i2 && j1 == j2)
    {
        return arr[i1][j1];
    }
    return arr[i1][j1] + arr[i2][j2];
}
 
// Recursive function to return the
// required maximum cost path
static int maxSumPath(int i1, int j1, int i2)
{
 
    // Column number of second path
    int j2 = i1 + j1 - i2;
 
    // Base Case
    if (i1 >= n || i2 >= n || j1 >= m || j2 >= m)
    {
        return 0;
    }
 
    // If already calculated, return from DP matrix
    if (cache[i1][j1][i2] != -1)
    {
        return cache[i1][j1][i2];
    }
    int ans = Integer.MIN_VALUE;
 
    // Recurring for neighbouring cells of both paths together
    ans = Math.max(ans, maxSumPath(i1 + 1, j1, i2 + 1) + sum(i1, j1, i2, j2));
    ans = Math.max(ans, maxSumPath(i1, j1 + 1, i2) + sum(i1, j1, i2, j2));
    ans = Math.max(ans, maxSumPath(i1, j1 + 1, i2 + 1) + sum(i1, j1, i2, j2));
    ans = Math.max(ans, maxSumPath(i1 + 1, j1, i2) + sum(i1, j1, i2, j2));
 
    // Saving result to the DP matrix for current state
    cache[i1][j1][i2] = ans;
 
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    //set initial value
    for(int i=0;i<5;i++)
    for(int i1=0;i1<5;i1++)
    for(int i2=0;i2<5;i2++)
    cache[i][i1][i2]=-1;
     
    System.out.println( maxSumPath(0, 0, 0));
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python 3 implementation of the approach
import sys
 
# Input matrix
n = 4
m = 4
arr = [[1, 0, 3, -1],
    [3, 5, 1, -2],
    [-2, 0, 1, 1],
    [2, 1, -1, 1]]
 
# DP matrix
cache = [[[-1 for i in range(5)] for j in range(5)] for k in range(5)]
 
# Function to return the sum of the cells
# arr[i1][j1] and arr[i2][j2]
def sum(i1, j1, i2, j2):
    if (i1 == i2 and j1 == j2):
        return arr[i1][j1]
    return arr[i1][j1] + arr[i2][j2]
 
# Recursive function to return the
# required maximum cost path
def maxSumPath(i1, j1, i2):
     
    # Column number of second path
    j2 = i1 + j1 - i2
 
    # Base Case
    if (i1 >= n or i2 >= n or j1 >= m or j2 >= m):
        return 0
 
    # If already calculated, return from DP matrix
    if (cache[i1][j1][i2] != -1):
        return cache[i1][j1][i2]
    ans = -sys.maxsize-1
 
    # Recurring for neighbouring cells of both paths together
    ans = max(ans, maxSumPath(i1 + 1, j1, i2 + 1) + sum(i1, j1, i2, j2))
    ans = max(ans, maxSumPath(i1, j1 + 1, i2) + sum(i1, j1, i2, j2))
    ans = max(ans, maxSumPath(i1, j1 + 1, i2 + 1) + sum(i1, j1, i2, j2))
    ans = max(ans, maxSumPath(i1 + 1, j1, i2) + sum(i1, j1, i2, j2))
 
    # Saving result to the DP matrix for current state
    cache[i1][j1][i2] = ans
 
    return ans
 
# Driver code
if __name__ == '__main__':
    print(maxSumPath(0, 0, 0))
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
// Input matrix
static int n = 4, m = 4;
static int [,]arr = { { 1, 0, 3, -1 },
                { 3, 5, 1, -2 },
                { -2, 0, 1, 1 },
                { 2, 1, -1, 1 } };
 
// DP matrix
static int [,,]cache = new int[5, 5, 5];
 
// Function to return the sum of the cells
// arr[i1][j1] and arr[i2][j2]
static int sum(int i1, int j1, int i2, int j2)
{
    if (i1 == i2 && j1 == j2)
    {
        return arr[i1, j1];
    }
    return arr[i1, j1] + arr[i2, j2];
}
 
// Recursive function to return the
// required maximum cost path
static int maxSumPath(int i1, int j1, int i2)
{
 
    // Column number of second path
    int j2 = i1 + j1 - i2;
 
    // Base Case
    if (i1 >= n || i2 >= n || j1 >= m || j2 >= m)
    {
        return 0;
    }
 
    // If already calculated, return from DP matrix
    if (cache[i1, j1, i2] != -1)
    {
        return cache[i1, j1, i2];
    }
    int ans = int.MinValue;
 
    // Recurring for neighbouring cells of both paths together
    ans = Math.Max(ans, maxSumPath(i1 + 1, j1, i2 + 1) + sum(i1, j1, i2, j2));
    ans = Math.Max(ans, maxSumPath(i1, j1 + 1, i2) + sum(i1, j1, i2, j2));
    ans = Math.Max(ans, maxSumPath(i1, j1 + 1, i2 + 1) + sum(i1, j1, i2, j2));
    ans = Math.Max(ans, maxSumPath(i1 + 1, j1, i2) + sum(i1, j1, i2, j2));
 
    // Saving result to the DP matrix for current state
    cache[i1, j1, i2] = ans;
 
    return ans;
}
 
// Driver code
public static void Main(String []args)
{
    //set initial value
    for(int i = 0; i < 5; i++)
        for(int i1 = 0; i1 < 5; i1++)
            for(int i2 = 0; i2 < 5; i2++)
                cache[i,i1,i2]=-1;
     
    Console.WriteLine( maxSumPath(0, 0, 0));
}
}
 
// This code contributed by Rajput-Ji

Javascript

<script>
// Javascript implementation of the approach
 
// Input matrix
let n = 4, m = 4;
let arr=[[ 1, 0, 3, -1 ],
                [ 3, 5, 1, -2 ],
                [ -2, 0, 1, 1 ],
                [ 2, 1, -1, 1 ]];
                 
// DP matrix
let cache=new Array(5);
for(let i = 0; i < 5; i++)
{
    cache[i] = new Array(5);
    for(let j = 0; j < 5; j++)
    {
        cache[i][j] = new Array(5);
        for(let k = 0; k < 5; k++)
        {
            cache[i][j][k] = -1;
        }
    }
}
 
// Function to return the sum of the cells
// arr[i1][j1] and arr[i2][j2]
function sum(i1, j1, i2, j2)
{
    if (i1 == i2 && j1 == j2)
    {
        return arr[i1][j1];
    }
    return arr[i1][j1] + arr[i2][j2];
}
 
// Recursive function to return the
// required maximum cost path
function maxSumPath(i1,j1,i2)
{
    // Column number of second path
    let j2 = i1 + j1 - i2;
   
    // Base Case
    if (i1 >= n || i2 >= n || j1 >= m || j2 >= m)
    {
        return 0;
    }
   
    // If already calculated, return from DP matrix
    if (cache[i1][j1][i2] != -1)
    {
        return cache[i1][j1][i2];
    }
    let ans = Number.MIN_VALUE;
   
    // Recurring for neighbouring cells of both paths together
    ans = Math.max(ans, maxSumPath(i1 + 1, j1, i2 + 1) + sum(i1, j1, i2, j2));
    ans = Math.max(ans, maxSumPath(i1, j1 + 1, i2) + sum(i1, j1, i2, j2));
    ans = Math.max(ans, maxSumPath(i1, j1 + 1, i2 + 1) + sum(i1, j1, i2, j2));
    ans = Math.max(ans, maxSumPath(i1 + 1, j1, i2) + sum(i1, j1, i2, j2));
   
    // Saving result to the DP matrix for current state
    cache[i1][j1][i2] = ans;
   
    return ans;
}
 
// Driver code
document.write( maxSumPath(0, 0, 0));
 
// This code is contributed by avanitrachhadiya2155
</script>
Producción: 

16

 

Complejidad del Tiempo: O((N 2 ) * M)
 

Publicación traducida automáticamente

Artículo escrito por _Gaurav_Tiwari y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *