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++
// 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
// 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
# 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#
// 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 // 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. ?>
Javascript
<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 2 ).
Espacio Auxiliar: O(n 2 ).
Ejercicio: Intenta resolverlo en espacio auxiliar de O(n).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA