Encuentre la suma máxima de rutas en una array 2D cuando se permiten exactamente dos movimientos a la izquierda

Dada una array 2D arr[][] de dimensiones N * M donde N es el número de filas y M es el número de columnas. La tarea es encontrar la suma máxima de rutas en esta array que satisfaga algunas condiciones que son las siguientes:

Solo podemos comenzar con arr[i][M] donde 0 <= i <= N.
Terminamos el camino en el mismo lado, de manera que podemos tomar exactamente 2 giros a la izquierda.

Ejemplo :
2D matrix showing path

Ejemplos:

Input : N = 3, M = 3
        arr[][] = {{1, 2, 3},
                   {3, 3, 1},
                   {4, 1, 6}}
Output : 20
Explanation : 
If we follow this path then we get the sum 20.

Input : N = 3, M = 3
        arr[][] = {{3, 7, 4},
                   {1, 9, 6},
                   {1, 7, 7}}
Output : 34
Explanation : 
If we follow this path then we get the sum 34.

La idea es usar programación dinámica y seleccionar una estructura óptima en la array, es decir , una estructura en
forma de C como se muestra en la imagen de abajo.

Los pasos son los siguientes :

Primero calculamos la suma del sufijo en cada fila y la almacenamos en otra array 2D, llámela b[][] para que en cada índice válido obtengamos la suma de toda la fila a partir de ese índice.

b[i][j] = arr[i][j] + b[i][j + 1]
Ahora verificamos cada dos filas consecutivas y encontramos la suma de sus columnas correspondientes y, al mismo tiempo, actualizamos la variable de suma máxima. Hasta ahora hemos encontrado ambas líneas horizontales de esa estructura anterior.

suma = max(suma, b[i][j] + b[i – 1][j])

Necesitamos encontrar esa línea vertical que conecta estas líneas horizontales, es decir, la columna.
Después de atravesar cada fila, para cada índice válido tenemos dos opciones: vinculamos este índice al índice correspondiente de la fila superior, es decir, agregamos en la columna anterior o comenzamos una nueva columna.
Cualquiera que sea el valor máximo, conservamos ese valor y actualizamos el valor en este índice.

b[i][j] = max(b[i][j], b[i – 1][j] + arr[i][j])

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to find maximum path sum
// in a 2D matrix when exactly two
// left moves are allowed
#include <bits/stdc++.h>
#define N 3
#define M 3
using namespace std;
  
// Function to return the maximum path sum
int findMaxSum(int arr[][M])
{
    int sum = 0;
    int b[N][M];
      
    // Copy last column i.e. starting and 
    // ending columns in another array
    for (int i = 0; i < N; i++) {
        b[i][M - 1] = arr[i][M - 1];
    }
      
    // Calculate suffix sum in each row
    for (int i = 0; i < N; i++) {
        for (int j = M - 2; j >= 0; j--) {
            b[i][j] = arr[i][j] + b[i][j + 1];
        }
    }
      
    // Select the path we are going to follow
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < M; j++) {
            sum = max(sum, b[i][j] + b[i - 1][j]);
              
            b[i][j] = max(b[i][j], b[i - 1][j] + arr[i][j]);
        }
    }
      
    return sum;
}
  
// Driver Code
int main()
{
    int arr[N][M] = {{ 3, 7, 4 }, 
                     { 1, 9, 6 }, 
                     { 1, 7, 7 }};
                       
    cout << findMaxSum(arr) << endl;
  
    return 0;
}

Java

// Java program to find maximum path sum
// in a 2D matrix when exactly two
// left moves are allowed
import java.io.*;
  
class GFG 
{
      
static int N = 3;
static int M = 3;
  
// Function to return the maximum path sum
static int findMaxSum(int arr[][])
{
    int sum = 0;
    int [][]b = new int [N][M];
      
    // Copy last column i.e. starting and 
    // ending columns in another array
    for (int i = 0; i < N; i++) 
    {
        b[i][M - 1] = arr[i][M - 1];
    }
      
    // Calculate suffix sum in each row
    for (int i = 0; i < N; i++) 
    {
        for (int j = M - 2; j >= 0; j--) 
        {
            b[i][j] = arr[i][j] + b[i][j + 1];
        }
    }
      
    // Select the path we are going to follow
    for (int i = 1; i < N; i++) 
    {
        for (int j = 0; j < M; j++) 
        {
            sum = Math.max(sum, b[i][j] + b[i - 1][j]);
              
            b[i][j] = Math.max(b[i][j], b[i - 1][j] + arr[i][j]);
        }
    }
      
    return sum;
}
  
// Driver Code
public static void main (String[] args) 
{
  
    int arr[][] = {{ 3, 7, 4 }, 
                    { 1, 9, 6 }, 
                    { 1, 7, 7 }};
                  
    System.out.println (findMaxSum(arr));
}
}
  
// This code is contributed by ajit.

Python3

# Python3 program to find maximum path sum 
# in a 2D matrix when exactly two 
# left moves are allowed 
import numpy as np
N = 3
M = 3
  
# Function to return the maximum path sum 
def findMaxSum(arr) : 
  
    sum = 0; 
    b = np.zeros((N, M)); 
      
    # Copy last column i.e. starting and 
    # ending columns in another array 
    for i in range(N) : 
        b[i][M - 1] = arr[i][M - 1]; 
      
    # Calculate suffix sum in each row 
    for i in range(N) :
        for j in range(M - 2, -1, -1) : 
            b[i][j] = arr[i][j] + b[i][j + 1]; 
      
    # Select the path we are going to follow 
    for i in range(1, N) :
        for j in range(M) :
            sum = max(sum, b[i][j] + b[i - 1][j]); 
              
            b[i][j] = max(b[i][j], 
                          b[i - 1][j] + arr[i][j]);
              
    return sum; 
  
# Driver Code 
if __name__ == "__main__" : 
  
    arr = [[ 3, 7, 4 ], 
           [ 1, 9, 6 ], 
           [ 1, 7, 7 ]]; 
                      
    print(findMaxSum(arr)); 
  
# This code is contributed by AnkitRai01

C#

// C# program to find maximum path sum
// in a 2D matrix when exactly two
// left moves are allowed
using System;
      
class GFG 
{
      
static int N = 3;
static int M = 3;
  
// Function to return the maximum path sum
static int findMaxSum(int [,]arr)
{
    int sum = 0;
    int [,]b = new int [N, M];
      
    // Copy last column i.e. starting and 
    // ending columns in another array
    for (int i = 0; i < N; i++) 
    {
        b[i, M - 1] = arr[i, M - 1];
    }
      
    // Calculate suffix sum in each row
    for (int i = 0; i < N; i++) 
    {
        for (int j = M - 2; j >= 0; j--) 
        {
            b[i, j] = arr[i, j] + b[i, j + 1];
        }
    }
      
    // Select the path we are going to follow
    for (int i = 1; i < N; i++) 
    {
        for (int j = 0; j < M; j++) 
        {
            sum = Math.Max(sum, b[i, j] + b[i - 1, j]);
              
            b[i, j] = Math.Max(b[i, j], b[i - 1, j] + arr[i, j]);
        }
    }
      
    return sum;
}
  
// Driver Code
public static void Main() 
{
  
    int [,]arr = {{ 3, 7, 4 }, 
                    { 1, 9, 6 }, 
                    { 1, 7, 7 }};
                  
    Console.WriteLine(findMaxSum(arr));
}
}
  
/* This code contributed by PrinciRaj1992 */

Producción:

Complejidad del tiempo: $O(N * M)$

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Deja una respuesta Cancelar la respuesta