Suma máxima de ruta en array

Dada una array de N * M. Encuentre la suma máxima de caminos en la array. La ruta máxima es la suma de todos los elementos desde la primera fila hasta la última fila donde solo se le permite moverse hacia abajo o en diagonal hacia la izquierda o la derecha. Puede comenzar desde cualquier elemento en la primera fila.

Ejemplos: 

Input : mat[][] = 10 10  2  0 20  4
                   1  0  0 30  2  5
                   0 10  4  0  2  0
                   1  0  2 20  0  4
Output : 74
The maximum sum path is 20-30-4-20.

Input : mat[][] = 1 2 3
                  9 8 7
                  4 5 6
Output : 17
The maximum sum path is 3-8-6.

Nos dan una array de N * M. Para encontrar la suma máxima de la ruta, primero tenemos que encontrar el valor máximo en la primera fila de la array. Guarde este valor en res. Ahora, para cada elemento en el elemento de actualización de array con valor máximo que se puede incluir en la ruta máxima. Si el valor es mayor que res, actualice res. En la última resolución de retorno, que consiste en el valor máximo de la suma de la ruta.

Implementación:

C++

// CPP program for finding max path in matrix
#include <bits/stdc++.h>
#define N 4
#define M 6
using namespace std;
 
// To calculate max path in matrix
int findMaxPath(int mat[][M])
{
 
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < M; j++) {
 
            // When all paths are possible
            if (j > 0 && j < M - 1)
                mat[i][j] += max(mat[i - 1][j],
                             max(mat[i - 1][j - 1],
                             mat[i - 1][j + 1]));
 
            // When diagonal right is not possible
            else if (j > 0)
                mat[i][j] += max(mat[i - 1][j],
                            mat[i - 1][j - 1]);
 
            // When diagonal left is not possible
            else if (j < M - 1)
                mat[i][j] += max(mat[i - 1][j],
                            mat[i - 1][j + 1]);
 
            // Store max path sum
        }
    }
    int res = 0;
    for (int j = 0; j < M; j++)
        res = max(mat[N-1][j], res);
    return res;
}
 
// Driver program to check findMaxPath
int main()
{
     
    int mat1[N][M] = { { 10, 10, 2, 0, 20, 4 },
                    { 1, 0, 0, 30, 2, 5 },
                    { 0, 10, 4, 0, 2, 0 },
                    { 1, 0, 2, 20, 0, 4 } };
             
    cout << findMaxPath(mat1) << endl;
    return 0;
}

Java

// Java program for finding max path in matrix
 
import static java.lang.Math.max;
 
class GFG
{
    public static int N = 4, M = 6;
     
    // Function to calculate max path in matrix
    static int findMaxPath(int mat[][])
    {
        // To find max val in first row
        int res = -1;
        for (int i = 0; i < M; i++)
            res = max(res, mat[0][i]);
 
        for (int i = 1; i < N; i++)
        {
            res = -1;
            for (int j = 0; j < M; j++)
            {
                // When all paths are possible
                if (j > 0 && j < M - 1)
                    mat[i][j] += max(mat[i - 1][j],
                                 max(mat[i - 1][j - 1],
                                    mat[i - 1][j + 1]));
 
                // When diagonal right is not possible
                else if (j > 0)
                    mat[i][j] += max(mat[i - 1][j],
                                    mat[i - 1][j - 1]);
 
                // When diagonal left is not possible
                else if (j < M - 1)
                    mat[i][j] += max(mat[i - 1][j],
                                mat[i - 1][j + 1]);
 
                // Store max path sum
                res = max(mat[i][j], res);
            }
        }
        return res;
    }
     
    // driver program
    public static void main (String[] args)
    {
        int mat[][] = { { 10, 10, 2, 0, 20, 4 },
                        { 1, 0, 0, 30, 2, 5 },
                        { 0, 10, 4, 0, 2, 0 },
                        { 1, 0, 2, 20, 0, 4 }
                    };
 
        System.out.println(findMaxPath(mat));
    }
}
 
// Contributed by Pramod Kumar

Python3

# Python 3 program for finding max path in matrix
# To calculate max path in matrix
 
def findMaxPath(mat):
   
    for i in range(1, N):
  
        res = -1
        for j in range(M):
  
            # When all paths are possible
            if (j > 0 and j < M - 1):
                mat[i][j] += max(mat[i - 1][j],
                                 max(mat[i - 1][j - 1],
                                     mat[i - 1][j + 1]))
  
            # When diagonal right is not possible
            else if (j > 0):
                mat[i][j] += max(mat[i - 1][j],
                                 mat[i - 1][j - 1])
  
            # When diagonal left is not possible
            else if (j < M - 1):
                mat[i][j] += max(mat[i - 1][j],
                                 mat[i - 1][j + 1])
  
            # Store max path sum
            res = max(mat[i][j], res)
    return res
 
# Driver program to check findMaxPath
N=4
M=6
mat = ([[ 10, 10, 2, 0, 20, 4 ],
        [ 1, 0, 0, 30, 2, 5 ],
        [ 0, 10, 4, 0, 2, 0 ],
        [ 1, 0, 2, 20, 0, 4 ]])
               
print(findMaxPath(mat))
 
# This code is contributed by Azkia Anam.

C#

// C# program for finding
// max path in matrix
using System;
 
class GFG
{
    static int N = 4, M = 6;
     
    // find the max element
    static int max(int a, int b)
    {
        if(a > b)
        return a;
        else
        return b;
    }
     
    // Function to calculate
    // max path in matrix
    static int findMaxPath(int [,]mat)
    {
        // To find max val
        // in first row
        int res = -1;
        for (int i = 0; i < M; i++)
            res = max(res, mat[0, i]);
 
        for (int i = 1; i < N; i++)
        {
            res = -1;
            for (int j = 0; j < M; j++)
            {
                // When all paths are possible
                if (j > 0 && j < M - 1)
                    mat[i, j] += max(mat[i - 1, j],
                                 max(mat[i - 1, j - 1],
                                     mat[i - 1, j + 1]));
 
                // When diagonal right
                // is not possible
                else if (j > 0)
                    mat[i, j] += max(mat[i - 1, j],
                                     mat[i - 1, j - 1]);
 
                // When diagonal left
                // is not possible
                else if (j < M - 1)
                    mat[i, j] += max(mat[i - 1, j],
                                 mat[i - 1, j + 1]);
 
                // Store max path sum
                res = max(mat[i, j], res);
            }
        }
        return res;
    }
     
    // Driver code
    static public void Main (String[] args)
    {
        int[,] mat = {{10, 10, 2, 0, 20, 4},
                      {1, 0, 0, 30, 2, 5},
                      {0, 10, 4, 0, 2, 0},
                      {1, 0, 2, 20, 0, 4}};
 
        Console.WriteLine(findMaxPath(mat));
    }
}
 
// This code is contributed
// by Arnab Kundu

PHP

<?php
// PHP program for finding max
// path in matrix
$N = 4;
$M = 6;
 
// To calculate max path in matrix
function findMaxPath($mat)
{
    global $N;
    global $M;
    for ($i = 1; $i < $N; $i++)
    {
        for ( $j = 0; $j < $M; $j++)
        {
 
            // When all paths are possible
            if ($j > 0 && $j < ($M - 1))
                $mat[$i][$j] += max($mat[$i - 1][$j],
                                max($mat[$i - 1][$j - 1],
                                    $mat[$i - 1][$j + 1]));
 
            // When diagonal right is
            // not possible
            else if ($j > 0)
                $mat[$i][$j] += max($mat[$i - 1][$j],
                                    $mat[$i - 1][$j - 1]);
 
            // When diagonal left is
            // not possible
            else if ($j < ($M - 1))
                $mat[$i][$j] += max($mat[$i - 1][$j],
                                    $mat[$i - 1][$j + 1]);
 
            // Store max path sum
        }
    }
     
    $res = 0;
    for ($j = 0; $j < $M; $j++)
        $res = max($mat[$N - 1][$j], $res);
    return $res;
}
 
// Driver Code
$mat1 = array( array( 10, 10, 2, 0, 20, 4 ),
               array( 1, 0, 0, 30, 2, 5 ),
               array( 0, 10, 4, 0, 2, 0 ),
               array( 1, 0, 2, 20, 0, 4 ));
         
echo findMaxPath($mat1),"\n";
 
// This code is contributed by Sach_Code
?>

Javascript

<script>
 
// Javascript program for finding max path in matrix
let N = 4, M = 6;
     
// Function to calculate max path in matrix
function findMaxPath(mat)
{
     
    // To find max val in first row
    let res = -1;
    for(let i = 0; i < M; i++)
        res = Math.max(res, mat[0][i]);
 
    for(let i = 1; i < N; i++)
    {
        res = -1;
        for(let j = 0; j < M; j++)
        {
             
            // When all paths are possible
            if (j > 0 && j < M - 1)
                mat[i][j] += Math.max(mat[i - 1][j],
                             Math.max(mat[i - 1][j - 1],
                                      mat[i - 1][j + 1]));
 
            // When diagonal right is not possible
            else if (j > 0)
                mat[i][j] += Math.max(mat[i - 1][j],
                                      mat[i - 1][j - 1]);
  
            // When diagonal left is not possible
            else if (j < M - 1)
                mat[i][j] += Math.max(mat[i - 1][j],
                                      mat[i - 1][j + 1]);
 
            // Store max path sum
            res = Math.max(mat[i][j], res);
        }
    }
    return res;
}
 
// Driver Code
let mat = [ [ 10, 10, 2, 0, 20, 4 ],
            [ 1, 0, 0, 30, 2, 5 ],
            [ 0, 10, 4, 0, 2, 0 ],
            [ 1, 0, 2, 20, 0, 4 ] ];
 
document.write(findMaxPath(mat));
    
// This code is contributed by sravan kumar
 
</script>
Producción

74

Complejidad temporal: O(N*M) , donde N y M son las dimensiones de la array
Complejidad espacial: O(1)

Este artículo es una contribución de nuclode . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *