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

Considere una array *n. Supongamos que cada celda de la array tiene un valor asignado. Podemos pasar de cada celda en la fila i a una celda diagonalmente más alta en la fila i+1 solamente [es decir, de celda(i, j) a celda(i+1, j-1) y celda(i+1, j+1 ) solamente]. Encuentre el camino de la fila superior a la fila inferior siguiendo la condición antes mencionada de manera que se obtenga la suma máxima.

Ejemplos:  

Input : mat[][] = { {5, 6, 1, 7},
                {-2, 10, 8, -1},
                {3, -7, -9, 11},
                {12, -4, 2, 6} }
Output : 28

{5, 6, 1, 7},
{-2, 10, 8, -1},
{3, -7, -9, 11},
{12, -4, 2, 6} }

The highlighted numbers from top to bottom
gives the required maximum sum path.
(7 + 8 + 11 + 2) = 28

Algoritmo: la idea es encontrar la suma máxima o todas las rutas comenzando con cada celda de la primera fila y finalmente devolver el máximo de todos los valores en la primera fila. Usamos Programación Dinámica ya que los resultados de muchos subproblemas son necesarios una y otra vez.

Implementación:

// C++ implementation to find the maximum sum
// path in a matrix
#include <bits/stdc++.h>
using namespace std;
 
#define SIZE 10
 
// function to find the maximum sum
// path in a matrix
int maxSum(int mat[SIZE][SIZE], int n)
{
    // if there is a single element only
    if (n == 1)
        return mat[0][0];
 
    // dp[][] matrix to store the results
    // of each iteration
    int dp[n][n];
    int maxSum = INT_MIN, max;
 
    // base case, copying elements of
    // last row
    for (int j = 0; j < n; j++)
        dp[n - 1][j] = mat[n - 1][j];
 
    // building up the dp[][] matrix from
    // bottom to the top row
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            max = INT_MIN;
 
            // finding the maximum diagonal element in the
            // (i+1)th row if that cell exists
            if (((j - 1) >= 0) && (max < dp[i + 1][j - 1]))
                max = dp[i + 1][j - 1];
            if (((j + 1) < n) && (max < dp[i + 1][j + 1]))
                max = dp[i + 1][j + 1];
 
            // adding that 'max' element to the
            // mat[i][j] element
            dp[i][j] = mat[i][j] + max;
        }
    }
 
    // finding the maximum value from the
    // first row of dp[][]
    for (int j = 0; j < n; j++)
        if (maxSum < dp[0][j])
            maxSum = dp[0][j];
 
    // required maximum sum
    return maxSum;
}
 
// Driver program to test above
int main()
{
    int mat[SIZE][SIZE] = { { 5, 6, 1, 7 },
                            { -2, 10, 8, -1 },
                            { 3, -7, -9, 11 },
                            { 12, -4, 2, 6 } };
    int n = 4;
 
    cout << "Maximum Sum = "
         << maxSum(mat, n);
 
    return 0;
}

// Java implementation to find the
// maximum sum path in a matrix
import java.io.*;
 
class MaxSumPath {
//int mat[][];
 
// function to find the maximum
// sum path in a matrix
static int maxSum(int[][] mat, int n)
{
    // if there is a single element only
    if (n == 1)
        return mat[0][0];
 
    // dp[][] matrix to store the results
    // of each iteration
    int dp[][] = new int[n][n];
    int maxSum = Integer.MIN_VALUE, max;
 
    // base case, copying elements of
    // last row
    for (int j = 0; j < n; j++)
        dp[n - 1][j] = mat[n - 1][j];
 
    // building up the dp[][] matrix
    // from bottom to the top row
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            max = Integer.MIN_VALUE;
 
            // finding the maximum diagonal
            // element in the (i+1)th row
            // if that cell exists
            if (((j - 1) >= 0) &&
                 (max < dp[i + 1][j - 1]))
                 max = dp[i + 1][j - 1];
            if (((j + 1) < n) &&
                (max < dp[i + 1][j + 1]))
                max = dp[i + 1][j + 1];
 
            // adding that 'max' element
            // to the mat[i][j] element
            dp[i][j] = mat[i][j] + max;
        }
    }
 
    // finding the maximum value from
    // the first row of dp[][]
    for (int j = 0; j < n; j++)
        if (maxSum < dp[0][j])
            maxSum = dp[0][j];
 
    // required maximum sum
    return maxSum;
}
 
    // Driver code
    public static void main (String[] args) {
     
    int mat[][] = { { 5, 6, 1, 7 },
                    { -2, 10, 8, -1 },
                    { 3, -7, -9, 11 },
                    { 12, -4, 2, 6 } };
    int n = 4;
 
    System.out.println("Maximum Sum = "+
                        maxSum(mat , n));
 
    }
}
 
// This code is contributed by Prerna Saini

# Python3 implementation to find
# the maximum sum path in a matrix
 
SIZE=10
INT_MIN=-10000000
 
# function to find the maximum sum
# path in a matrix
def maxSum(mat,n):
     
    #if there is a single elementif
    #there is a single element only
    if n==1:
        return mat[0][0]
         
    # dp[][] matrix to store the results
    # of each iteration
    dp=[[0 for i in range(n)]for i in range(n)]
    maxSum=INT_MIN
     
    # base case, copying elements of
    # last row
    for j in range(n):
        dp[n - 1][j] = mat[n - 1][j]
         
    # building up the dp[][] matrix from
    # bottom to the top row
    for i in range(n-2,-1,-1):
        for j in range(n):
            maxi=INT_MIN
             
            # finding the maximum diagonal
            # element in the
            # (i+1)th row if that cell exists
            if ((((j - 1) >= 0) and
               (maxi < dp[i + 1][j - 1]))):
                   maxi = dp[i + 1][j - 1]
            if ((((j + 1) < n) and
               (maxi < dp[i + 1][j + 1]))):
                   maxi = dp[i + 1][j + 1]
                 
            # adding that 'max' element to the
            # mat[i][j] element
            dp[i][j] = mat[i][j] + maxi
             
    # finding the maximum value from the
    # first row of dp[][]
    for j in range(n):
        if (maxSum < dp[0][j]):
            maxSum = dp[0][j]
             
    # required maximum sum
    return maxSum
 
# Driver program to test above
if __name__=='__main__':
    mat=[[5, 6, 1, 7],
        [-2, 10, 8, -1],
        [ 3, -7, -9, 11 ],
        [12, -4, 2, 6 ]]
 
    n=4
    print("Maximum Sum=",maxSum(mat,n))
     
#This code is contributed by sahilshelangia

// C# implementation to find the
// maximum sum path in a matrix
using System;
 
class MaxSumPath
{
    //int mat[][];
     
    // function to find the maximum
    // sum path in a matrix
    static int maxSum(int[,] mat, int n)
    {
        // if there is a single element only
        if (n == 1)
            return mat[0, 0];
     
        // dp[][] matrix to store the results
        // of each iteration
        int [,]dp = new int[n, n];
        int maxSum = int.MinValue, max;
     
        // base case, copying elements of
        // last row
        for (int j = 0; j < n; j++)
            dp[n - 1, j] = mat[n - 1, j];
     
        // building up the dp[][] matrix
        // from bottom to the top row
        for (int i = n - 2; i >= 0; i--)
        {
            for (int j = 0; j < n; j++)
            {
                max = int.MinValue;
     
                // finding the maximum diagonal
                // element in the (i+1)th row
                // if that cell exists
                if (((j - 1) >= 0) &&
                    (max < dp[i + 1, j - 1]))
                    max = dp[i + 1, j - 1];
                if (((j + 1) < n) &&
                    (max < dp[i + 1, j + 1]))
                    max = dp[i + 1, j + 1];
     
                // adding that 'max' element
                // to the mat[i][j] element
                dp[i, j] = mat[i, j] + max;
            }
        }
     
        // finding the maximum value from
        // the first row of dp[][]
        for (int j = 0; j < n; j++)
            if (maxSum < dp[0, j])
                maxSum = dp[0, j];
     
        // required maximum sum
        return maxSum;
    }
 
    // Driver code
    public static void Main () {
     
    int [,]mat = { { 5, 6, 1, 7 },
                    { -2, 10, 8, -1 },
                    { 3, -7, -9, 11 },
                    { 12, -4, 2, 6 } };
    int n = 4;
 
    Console.WriteLine("Maximum Sum = "+
                        maxSum(mat , n));
 
    }
}
 
// This code is contributed by vt_m

<?php
// PHP implementation to find
// the maximum sum path in a matrix
 
$SIZE = 10;
 
// function to find the maximum sum
// path in a matrix
function maxSum( $mat, $n)
{
     
    // if there is a single
    // element only
    if ($n == 1)
        return $mat[0][0];
 
    // dp[][] matrix to store the results
    // of each iteration
    $dp = array(array());
    $maxSum = PHP_INT_MIN;
    $max;
 
    // base case, copying elements of
    // last row
    for($j = 0; $j < $n; $j++)
        $dp[$n - 1][$j] = $mat[$n - 1][$j];
 
    // building up the dp[][] matrix from
    // bottom to the top row
    for ( $i = $n - 2; $i >= 0; $i--)
    {
        for ( $j = 0; $j < $n; $j++)
        {
            $max = PHP_INT_MIN;
 
            // finding the maximum
            // diagonal element in the
            // (i+1)th row if that cell
            // exists
            if ((($j - 1) >= 0) and
                ($max < $dp[$i + 1][$j - 1]))
                 
                $max = $dp[$i + 1][$j - 1];
                 
            if ((($j + 1) < $n) and ($max <
                      $dp[$i + 1][$j + 1]))
                       
                $max = $dp[$i + 1][$j + 1];
 
            // adding that 'max' element to the
            // mat[i][j] element
            $dp[$i][$j] = $mat[$i][$j] + $max;
        }
    }
 
    // finding the maximum value from the
    // first row of dp[][]
    for ( $j = 0; $j < $n; $j++)
        if ($maxSum < $dp[0][$j])
            $maxSum = $dp[0][$j];
 
    // required maximum sum
    return $maxSum;
}
 
    // Driver Code
    $mat = array(array(5, 6, 1, 7),
                 array(-2, 10, 8, -1),
                 array(3, -7, -9, 11),
                 array(12, -4, 2, 6));
    $n = 4;
    echo "Maximum Sum = "
        , maxSum($mat, $n);
 
// This code is contributed by anuj_67.
?>

<script>
 
// JavaScript implementation to find the
// maximum sum path in a matrix
 
// Function to find the maximum
// sum path in a matrix
function maxSum(mat, n)
{
     
    // If there is a single element only
    if (n == 1)
        return mat[0][0];
   
    // dp[][] matrix to store the results
    // of each iteration
    let dp = new Array(n);
      
    // Loop to create 2D array using 1D array
    for(var i = 0; i < dp.length; i++)
    {
        dp[i] = new Array(2);
    }
     
    let maxSum = Number.MIN_VALUE, max;
   
    // Base case, copying elements of
    // last row
    for(let j = 0; j < n; j++)
        dp[n - 1][j] = mat[n - 1][j];
   
    // Building up the dp[][] matrix
    // from bottom to the top row
    for(let i = n - 2; i >= 0; i--)
    {
        for(let j = 0; j < n; j++)
        {
            max = Number.MIN_VALUE;
             
            // Finding the maximum diagonal
            // element in the (i+1)th row
            // if that cell exists
            if (((j - 1) >= 0) &&
               (max < dp[i + 1][j - 1]))
                 max = dp[i + 1][j - 1];
            if (((j + 1) < n) &&
               (max < dp[i + 1][j + 1]))
                max = dp[i + 1][j + 1];
   
            // Adding that 'max' element
            // to the mat[i][j] element
            dp[i][j] = mat[i][j] + max;
        }
    }
   
    // Finding the maximum value from
    // the first row of dp[][]
    for(let j = 0; j < n; j++)
        if (maxSum < dp[0][j])
            maxSum = dp[0][j];
   
    // Required maximum sum
    return maxSum;
}
   
// Driver Code
let mat = [ [ 5, 6, 1, 7 ],
            [ -2, 10, 8, -1 ],
            [ 3, -7, -9, 11 ],
            [ 12, -4, 2, 6 ] ];
let n = 4;
 
document.write("Maximum Sum = "+
               maxSum(mat , n));
                
// This code is contributed by sanjoy_62
 
</script>

Maximum Sum = 28

Complejidad Temporal: O(n ² ). 
Espacio Auxiliar: O(n ² ).

Ejercicio: Intenta resolverlo en espacio auxiliar de O(n).