Dada una array 2D de tamaño N*M . La tarea es encontrar la ruta de producto máxima de (0, 0) a (N-1, M-1) . Solo puede moverse hacia la derecha de (i, j) a (i, j+1) y hacia abajo de (i, j) a (i+1, j) .
Ejemplos:
Entrada: arr[][] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }
Salida: 2016
La ruta con el producto máximo es: 1->4->7 ->8->9 = 2016
Aproximación:
Para elegir en qué dirección ir desde la posición actual tenemos que comprobar la dirección que da el máximo producto. Mantendremos dos arrays 2D:
- maxPath[i][j]: Almacenará el producto máximo hasta (i, j)
- minPath[i][j]: Almacenará el producto mínimo hasta (i, j)
Pasos:
- Inicialice maxPath[0][0] y minPath[0][0] en arr[0][0].
- Para todas las celdas restantes en maxPath[i][j], compruebe si el producto de la celda actual (i, j) y la celda anterior (i-1, j) es máximo o no:
considerando filas:
maxValue1 = max(arr[i][j]*maxPath[i-1][j], arr[i][j]*minPath[i-1][j])
considerando columnas:
maxValue2 = max( maxPath[i][j – 1] * arr[i][j], minPath[i][j – 1] * arr[i][j])
como arr[i][j] puede ser negativo y si minPath [i][j] es negativo. Entonces,
arr[i][j]*minPath[i][j] es positivo, lo que puede ser el producto máximo.
- Para todas las celdas restantes en minPath[i][j], compruebe si el producto de la celda actual (i, j) y la celda anterior (i-1, j) es mínimo o no:
considerando filas:
minValue1 = min(maxPath[i – 1][j] * arr[i][j], minPath[i – 1][j] * arr[i][j])
considerando columnas:
minValue2 = min( maxPath[i][j – 1] * arr[i][j], minPath[i][j – 1] * arr[i][j])
- Actualice minPath[i][j] = min(minValue1, minValue2) & maxPath[i][j] = max(maxValue1, maxValue2)
- Devuelve maxPath[n-1][m-1] para el producto máximo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find maximum
// product path from (0, 0) to
// (N-1, M-1)
#include <bits/stdc++.h>
using namespace std;
#define N 3
#define M 3
// Function to find maximum product
int maxProductPath(int arr[N][M])
{
// It will store the maximum
// product till a given cell.
vector<vector<int> > maxPath(N, vector<int>(M, INT_MIN));
// It will store the minimum
// product till a given cell
// (for -ve elements)
vector<vector<int> > minPath(N, vector<int>(M, INT_MAX));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int minVal = INT_MAX;
int maxVal = INT_MIN;
// If we are at topmost
// or leftmost, just
// copy the elements.
if (i == 0 && j == 0) {
maxVal = arr[i][j];
minVal = arr[i][j];
}
// If we're not at the
// above, we can consider
// the above value.
if (i > 0) {
int tempMax = max(maxPath[i - 1][j] * arr[i][j],
minPath[i - 1][j] * arr[i][j]);
maxVal = max(maxVal, tempMax);
int tempMin = min(maxPath[i - 1][j] * arr[i][j],
minPath[i - 1][j] * arr[i][j]);
minVal = min(minVal, tempMin);
}
// If we're not on the
// leftmost, we can consider
// the left value.
if (j > 0) {
int tempMax = max(maxPath[i][j - 1] * arr[i][j],
minPath[i][j - 1] * arr[i][j]);
maxVal = max(maxVal, tempMax);
int tempMin = min(maxPath[i][j - 1] * arr[i][j],
minPath[i][j - 1] * arr[i][j]);
minVal = min(minVal, tempMin);
}
// Store max & min product
// till i, j.
maxPath[i][j] = maxVal;
minPath[i][j] = minVal;
}
}
// Return the max product path
// from 0, 0 -> N-1, M-1.
return maxPath[N - 1][M - 1];
}
// Driver Code
int main()
{
int arr[N][M] = { { 1, -2, 3 },
{ 4, -5, 6 },
{ -7, -8, 9 } };
// Print maximum product from
// (0, 0) to (N-1, M-1)
cout << maxProductPath(arr) << endl;
return 0;
}
Java
// Java Program to find maximum
// product path from (0, 0) to
// (N-1, M-1)
class GFG
{
static final int N = 3;
static final int M = 3;
// Function to find maximum product
static int maxProductPath(int arr[][])
{
// It will store the maximum
// product till a given cell.
int [][]maxPath = new int[N][M];
// It will store the minimum
// product till a given cell
// (for -ve elements)
int [][]minPath = new int[N][M];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
int minVal = Integer.MAX_VALUE;
int maxVal = Integer.MIN_VALUE;
// If we are at topmost
// or leftmost, just
// copy the elements.
if (i == 0 && j == 0)
{
maxVal = arr[i][j];
minVal = arr[i][j];
}
// If we're not at the
// above, we can consider
// the above value.
if (i > 0)
{
int tempMax = Math.max(maxPath[i - 1][j] * arr[i][j],
minPath[i - 1][j] * arr[i][j]);
maxVal = Math.max(maxVal, tempMax);
int tempMin = Math.min(maxPath[i - 1][j] * arr[i][j],
minPath[i - 1][j] * arr[i][j]);
minVal = Math.min(minVal, tempMin);
}
// If we're not on the
// leftmost, we can consider
// the left value.
if (j > 0) {
int tempMax = Math.max(maxPath[i][j - 1] * arr[i][j],
minPath[i][j - 1] * arr[i][j]);
maxVal = Math.max(maxVal, tempMax);
int tempMin = Math.min(maxPath[i][j - 1] * arr[i][j],
minPath[i][j - 1] * arr[i][j]);
minVal = Math.min(minVal, tempMin);
}
// Store max & min product
// till i, j.
maxPath[i][j] = maxVal;
minPath[i][j] = minVal;
}
}
// Return the max product path
// from 0, 0.N-1, M-1.
return maxPath[N - 1][M - 1];
}
// Driver Code
public static void main(String[] args)
{
int arr[][] = { { 1, -2, 3 },
{ 4, -5, 6 },
{ -7, -8, 9 } };
// Print maximum product from
// (0, 0) to (N-1, M-1)
System.out.print(maxProductPath(arr) +"\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python Program to find maximum # product path from (0, 0) to # (N-1, M-1) import sys N = 3; M = 3; # Function to find maximum product def maxProductPath(arr): # It will store the maximum # product till a given cell. maxPath = [[0 for i in range(M)] for j in range(N)]; # It will store the minimum # product till a given cell # (for -ve elements) minPath = [[0 for i in range(M)] for j in range(N)]; for i in range(N): for j in range(M): minVal = sys.maxsize; maxVal = -sys.maxsize; # If we are at topmost # or leftmost, just # copy the elements. if (i == 0 and j == 0): maxVal = arr[i][j]; minVal = arr[i][j]; # If we're not at the # above, we can consider # the above value. if (i > 0): tempMax = max(maxPath[i - 1][j] * arr[i][j],\ minPath[i - 1][j] * arr[i][j]); maxVal = max(maxVal, tempMax); tempMin = min(maxPath[i - 1][j] * arr[i][j],\ minPath[i - 1][j] * arr[i][j]); minVal = min(minVal, tempMin); # If we're not on the # leftmost, we can consider # the left value. if (j > 0): tempMax = max(maxPath[i][j - 1] * arr[i][j],\ minPath[i][j - 1] * arr[i][j]); maxVal = max(maxVal, tempMax); tempMin = min(maxPath[i][j - 1] * arr[i][j],\ minPath[i][j - 1] * arr[i][j]); minVal = min(minVal, tempMin); # Store max & min product # till i, j. maxPath[i][j] = maxVal; minPath[i][j] = minVal; # Return the max product path # from 0, 0.N-1, M-1. return maxPath[N - 1][M - 1]; # Driver Code if __name__ == '__main__': arr = [[ 1, -2, 3 ],[ 4, -5, 6 ],[ -7, -8, 9]]; # Print maximum product from # (0, 0) to (N-1, M-1) print(maxProductPath(arr)); # This code is contributed by 29AjayKumar
C#
// C# Program to find maximum
// product path from (0, 0) to
// (N-1, M-1)
using System;
class GFG
{
static readonly int N = 3;
static readonly int M = 3;
// Function to find maximum product
static int maxProductPath(int [,]arr)
{
// It will store the maximum
// product till a given cell.
int [,]maxPath = new int[N, M];
// It will store the minimum
// product till a given cell
// (for -ve elements)
int [,]minPath = new int[N, M];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
int minVal = int.MaxValue;
int maxVal = int.MinValue;
// If we are at topmost
// or leftmost, just
// copy the elements.
if (i == 0 && j == 0)
{
maxVal = arr[i, j];
minVal = arr[i, j];
}
// If we're not at the
// above, we can consider
// the above value.
if (i > 0)
{
int tempMax = Math.Max(maxPath[i - 1,j] * arr[i,j],
minPath[i - 1,j] * arr[i,j]);
maxVal = Math.Max(maxVal, tempMax);
int tempMin = Math.Min(maxPath[i - 1,j] * arr[i,j],
minPath[i - 1,j] * arr[i,j]);
minVal = Math.Min(minVal, tempMin);
}
// If we're not on the
// leftmost, we can consider
// the left value.
if (j > 0) {
int tempMax = Math.Max(maxPath[i,j - 1] * arr[i,j],
minPath[i,j - 1] * arr[i,j]);
maxVal = Math.Max(maxVal, tempMax);
int tempMin = Math.Min(maxPath[i,j - 1] * arr[i,j],
minPath[i,j - 1] * arr[i,j]);
minVal = Math.Min(minVal, tempMin);
}
// Store max & min product
// till i, j.
maxPath[i, j] = maxVal;
minPath[i, j] = minVal;
}
}
// Return the max product path
// from 0, 0.N - 1, M - 1.
return maxPath[N - 1, M - 1];
}
// Driver Code
public static void Main(String[] args)
{
int [,]arr = { { 1, -2, 3 },
{ 4, -5, 6 },
{ -7, -8, 9 } };
// Print maximum product from
// (0, 0) to (N - 1, M - 1)
Console.Write(maxProductPath(arr) +"\n");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript Program to find maximum
// product path from (0, 0) to
// (N-1, M-1)
const N = 3;
const M = 3;
// Function to find maximum product
function maxProductPath(arr){
// It will store the maximum
// product till a given cell.
let maxPath = new Array(N);
for(let i=0;i<N;i++){
maxPath[i] = new Array(M).fill(0);
}
// It will store the minimum
// product till a given cell
// (for -ve elements)
let minPath = new Array(N);
for(let i=0;i<N;i++){
minPath[i] = new Array(M).fill(0);
}
for(let i=0;i<N;i++){
for(let j=0;j<M;j++){
let minVal = Number.MAX_VALUE;
let maxVal = Number.MIN_VALUE;
// If we are at topmost
// or leftmost, just
// copy the elements.
if (i == 0 && j == 0){
maxVal = arr[i][j];
minVal = arr[i][j];
}
// If we're not at the
// above, we can consider
// the above value.
if (i > 0){
tempMax = Math.max(maxPath[i - 1][j] * arr[i][j],
minPath[i - 1][j] * arr[i][j]);
maxVal = Math.max(maxVal, tempMax);
tempMin = Math.min(maxPath[i - 1][j] * arr[i][j],
minPath[i - 1][j] * arr[i][j]);
minVal = Math.min(minVal, tempMin);
}
// If we're not on the
// leftmost, we can consider
// the left value.
if (j > 0){
tempMax = Math.max(maxPath[i][j - 1] * arr[i][j],
minPath[i][j - 1] * arr[i][j]);
maxVal = Math.max(maxVal, tempMax);
tempMin = Math.min(maxPath[i][j - 1] * arr[i][j],
minPath[i][j - 1] * arr[i][j]);
minVal = Math.min(minVal, tempMin);
}
// Store max & min product
// till i, j.
maxPath[i][j] = maxVal;
minPath[i][j] = minVal;
}
}
// Return the max product path
// from 0, 0.N-1, M-1.
return maxPath[N - 1][M - 1];
}
// Driver Code
let arr = [[ 1, -2, 3 ],[ 4, -5, 6 ],[ -7, -8, 9]];
// Print maximum product from
// (0, 0) to (N-1, M-1)
document.write(maxProductPath(arr));
// This code is contributed by shinjanpatra
</script>
Producción:
2016
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA