Dada una array nxn mat[n][n] de enteros, encuentre el valor máximo de mat(c, d) – mat(a, b) sobre todas las opciones de índices tales que tanto c > a como d > b.
Ejemplo:
Input:
mat[N][N] = {{ 1, 2, -1, -4, -20 },
{ -8, -3, 4, 2, 1 },
{ 3, 8, 6, 1, 3 },
{ -4, -1, 1, 7, -6 },
{ 0, -4, 10, -5, 1 }};
Output: 18
The maximum value is 18 as mat[4][2]
- mat[1][0] = 18 has maximum difference.
El programa debe hacer solo UN recorrido de la array. es decir, la complejidad temporal esperada es O(n 2 )
Una solución sencilla sería aplicar la fuerza bruta. Para todos los valores mat(a, b) en la array, encontramos mat(c, d) que tiene un valor máximo tal que c > a y d > b y continúa actualizando el valor máximo encontrado hasta el momento. Finalmente devolvemos el valor máximo.
A continuación se muestra su implementación.
C++
// A Naive method to find maximum value of mat[d][e]
// - ma[a][b] such that d > a and e > b
#include <bits/stdc++.h>
using namespace std;
#define N 5
// The function returns maximum value A(d,e) - A(a,b)
// over all choices of indexes such that both d > a
// and e > b.
int findMaxValue(int mat[][N])
{
// stores maximum value
int maxValue = INT_MIN;
// Consider all possible pairs mat[a][b] and
// mat[d][e]
for (int a = 0; a < N - 1; a++)
for (int b = 0; b < N - 1; b++)
for (int d = a + 1; d < N; d++)
for (int e = b + 1; e < N; e++)
if (maxValue < (mat[d][e] - mat[a][b]))
maxValue = mat[d][e] - mat[a][b];
return maxValue;
}
// Driver program to test above function
int main()
{
int mat[N][N] = {
{ 1, 2, -1, -4, -20 },
{ -8, -3, 4, 2, 1 },
{ 3, 8, 6, 1, 3 },
{ -4, -1, 1, 7, -6 },
{ 0, -4, 10, -5, 1 }
};
cout << "Maximum Value is "
<< findMaxValue(mat);
return 0;
}
Java
// A Naive method to find maximum value of mat1[d][e]
// - ma[a][b] such that d > a and e > b
import java.io.*;
import java.util.*;
class GFG
{
// The function returns maximum value A(d,e) - A(a,b)
// over all choices of indexes such that both d > a
// and e > b.
static int findMaxValue(int N,int mat[][])
{
// stores maximum value
int maxValue = Integer.MIN_VALUE;
// Consider all possible pairs mat[a][b] and
// mat1[d][e]
for (int a = 0; a < N - 1; a++)
for (int b = 0; b < N - 1; b++)
for (int d = a + 1; d < N; d++)
for (int e = b + 1; e < N; e++)
if (maxValue < (mat[d][e] - mat[a][b]))
maxValue = mat[d][e] - mat[a][b];
return maxValue;
}
// Driver code
public static void main (String[] args)
{
int N = 5;
int mat[][] = {
{ 1, 2, -1, -4, -20 },
{ -8, -3, 4, 2, 1 },
{ 3, 8, 6, 1, 3 },
{ -4, -1, 1, 7, -6 },
{ 0, -4, 10, -5, 1 }
};
System.out.print("Maximum Value is " +
findMaxValue(N,mat));
}
}
// This code is contributed
// by Prakriti Gupta
Python 3
# A Naive method to find maximum
# value of mat[d][e] - mat[a][b]
# such that d > a and e > b
N = 5
# The function returns maximum
# value A(d,e) - A(a,b) over
# all choices of indexes such
# that both d > a and e > b.
def findMaxValue(mat):
# stores maximum value
maxValue = 0
# Consider all possible pairs
# mat[a][b] and mat[d][e]
for a in range(N - 1):
for b in range(N - 1):
for d in range(a + 1, N):
for e in range(b + 1, N):
if maxValue < int (mat[d][e] -
mat[a][b]):
maxValue = int(mat[d][e] -
mat[a][b]);
return maxValue;
# Driver Code
mat = [[ 1, 2, -1, -4, -20 ],
[ -8, -3, 4, 2, 1 ],
[ 3, 8, 6, 1, 3 ],
[ -4, -1, 1, 7, -6 ],
[ 0, -4, 10, -5, 1 ]];
print("Maximum Value is " +
str(findMaxValue(mat)))
# This code is contributed
# by ChitraNayal
C#
// A Naive method to find maximum
// value of mat[d][e] - mat[a][b]
// such that d > a and e > b
using System;
class GFG
{
// The function returns
// maximum value A(d,e) - A(a,b)
// over all choices of indexes
// such that both d > a
// and e > b.
static int findMaxValue(int N,
int [,]mat)
{
//stores maximum value
int maxValue = int.MinValue;
// Consider all possible pairs
// mat[a][b] and mat[d][e]
for (int a = 0; a< N - 1; a++)
for (int b = 0; b < N - 1; b++)
for (int d = a + 1; d < N; d++)
for (int e = b + 1; e < N; e++)
if (maxValue < (mat[d, e] -
mat[a, b]))
maxValue = mat[d, e] -
mat[a, b];
return maxValue;
}
// Driver code
public static void Main ()
{
int N = 5;
int [,]mat = {{1, 2, -1, -4, -20},
{-8, -3, 4, 2, 1},
{3, 8, 6, 1, 3},
{-4, -1, 1, 7, -6},
{0, -4, 10, -5, 1}};
Console.Write("Maximum Value is " +
findMaxValue(N,mat));
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// A Naive method to find maximum
// value of $mat[d][e] - ma[a][b]
// such that $d > $a and $e > $b
$N = 5;
// The function returns maximum
// value A(d,e) - A(a,b) over
// all choices of indexes such
// that both $d > $a and $e > $b.
function findMaxValue(&$mat)
{
global $N;
// stores maximum value
$maxValue = PHP_INT_MIN;
// Consider all possible
// pairs $mat[$a][$b] and
// $mat[$d][$e]
for ($a = 0; $a < $N - 1; $a++)
for ($b = 0; $b < $N - 1; $b++)
for ($d = $a + 1; $d < $N; $d++)
for ($e = $b + 1; $e < $N; $e++)
if ($maxValue < ($mat[$d][$e] -
$mat[$a][$b]))
$maxValue = $mat[$d][$e] -
$mat[$a][$b];
return $maxValue;
}
// Driver Code
$mat = array(array(1, 2, -1, -4, -20),
array(-8, -3, 4, 2, 1),
array(3, 8, 6, 1, 3),
array(-4, -1, 1, 7, -6),
array(0, -4, 10, -5, 1));
echo "Maximum Value is " .
findMaxValue($mat);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// A Naive method to find maximum value of mat1[d][e]
// - ma[a][b] such that d > a and e > b
// The function returns maximum value A(d,e) - A(a,b)
// over all choices of indexes such that both d > a
// and e > b.
function findMaxValue(N,mat)
{
// stores maximum value
let maxValue = Number.MIN_VALUE;
// Consider all possible pairs mat[a][b] and
// mat1[d][e]
for (let a = 0; a < N - 1; a++)
for (let b = 0; b < N - 1; b++)
for (let d = a + 1; d < N; d++)
for (let e = b + 1; e < N; e++)
if (maxValue < (mat[d][e] - mat[a][b]))
maxValue = mat[d][e] - mat[a][b];
return maxValue;
}
// Driver code
let N = 5;
let mat=[[ 1, 2, -1, -4, -20],[-8, -3, 4, 2, 1],[3, 8, 6, 1, 3],[ -4, -1, 1, 7, -6 ],[ 0, -4, 10, -5, 1 ]];
document.write("Maximum Value is " +findMaxValue(N,mat));
// This code is contributed by rag2127
</script>
Producción
Maximum Value is 18
Complejidad temporal: O(N 4) .
Espacio Auxiliar: O(1)
El programa anterior se ejecuta en tiempo O (n ^ 4), que no está cerca de la complejidad de tiempo esperada de O (n ^ 2)
Una solución eficiente utiliza espacio extra. Preprocesamos la array de modo que el índice (i, j) almacene el máximo de elementos en la array desde (i, j) hasta (N-1, N-1) y en el proceso continúa actualizando el valor máximo encontrado hasta el momento. Finalmente devolvemos el valor máximo.
Implementación:
C++
// An efficient method to find maximum value of mat[d]
// - ma[a][b] such that c > a and d > b
#include <bits/stdc++.h>
using namespace std;
#define N 5
// The function returns maximum value A(c,d) - A(a,b)
// over all choices of indexes such that both c > a
// and d > b.
int findMaxValue(int mat[][N])
{
//stores maximum value
int maxValue = INT_MIN;
// maxArr[i][j] stores max of elements in matrix
// from (i, j) to (N-1, N-1)
int maxArr[N][N];
// last element of maxArr will be same's as of
// the input matrix
maxArr[N-1][N-1] = mat[N-1][N-1];
// preprocess last row
int maxv = mat[N-1][N-1]; // Initialize max
for (int j = N - 2; j >= 0; j--)
{
if (mat[N-1][j] > maxv)
maxv = mat[N - 1][j];
maxArr[N-1][j] = maxv;
}
// preprocess last column
maxv = mat[N - 1][N - 1]; // Initialize max
for (int i = N - 2; i >= 0; i--)
{
if (mat[i][N - 1] > maxv)
maxv = mat[i][N - 1];
maxArr[i][N - 1] = maxv;
}
// preprocess rest of the matrix from bottom
for (int i = N-2; i >= 0; i--)
{
for (int j = N-2; j >= 0; j--)
{
// Update maxValue
if (maxArr[i+1][j+1] - mat[i][j] >
maxValue)
maxValue = maxArr[i + 1][j + 1] - mat[i][j];
// set maxArr (i, j)
maxArr[i][j] = max(mat[i][j],
max(maxArr[i][j + 1],
maxArr[i + 1][j]) );
}
}
return maxValue;
}
// Driver program to test above function
int main()
{
int mat[N][N] = {
{ 1, 2, -1, -4, -20 },
{ -8, -3, 4, 2, 1 },
{ 3, 8, 6, 1, 3 },
{ -4, -1, 1, 7, -6 },
{ 0, -4, 10, -5, 1 }
};
cout << "Maximum Value is "
<< findMaxValue(mat);
return 0;
}
Java
// An efficient method to find maximum value of mat1[d]
// - ma[a][b] such that c > a and d > b
import java.io.*;
import java.util.*;
class GFG
{
// The function returns maximum value A(c,d) - A(a,b)
// over all choices of indexes such that both c > a
// and d > b.
static int findMaxValue(int N,int mat[][])
{
//stores maximum value
int maxValue = Integer.MIN_VALUE;
// maxArr[i][j] stores max of elements in matrix
// from (i, j) to (N-1, N-1)
int maxArr[][] = new int[N][N];
// last element of maxArr will be same's as of
// the input matrix
maxArr[N-1][N-1] = mat[N-1][N-1];
// preprocess last row
int maxv = mat[N-1][N-1]; // Initialize max
for (int j = N - 2; j >= 0; j--)
{
if (mat[N-1][j] > maxv)
maxv = mat[N - 1][j];
maxArr[N-1][j] = maxv;
}
// preprocess last column
maxv = mat[N - 1][N - 1]; // Initialize max
for (int i = N - 2; i >= 0; i--)
{
if (mat[i][N - 1] > maxv)
maxv = mat[i][N - 1];
maxArr[i][N - 1] = maxv;
}
// preprocess rest of the matrix from bottom
for (int i = N-2; i >= 0; i--)
{
for (int j = N-2; j >= 0; j--)
{
// Update maxValue
if (maxArr[i+1][j+1] - mat[i][j] > maxValue)
maxValue = maxArr[i + 1][j + 1] - mat[i][j];
// set maxArr (i, j)
maxArr[i][j] = Math.max(mat[i][j],
Math.max(maxArr[i][j + 1],
maxArr[i + 1][j]) );
}
}
return maxValue;
}
// Driver code
public static void main (String[] args)
{
int N = 5;
int mat[][] = {
{ 1, 2, -1, -4, -20 },
{ -8, -3, 4, 2, 1 },
{ 3, 8, 6, 1, 3 },
{ -4, -1, 1, 7, -6 },
{ 0, -4, 10, -5, 1 }
};
System.out.print("Maximum Value is " +
findMaxValue(N,mat));
}
}
// Contributed by Prakriti Gupta
Python3
# An efficient method to find maximum value
# of mat[d] - ma[a][b] such that c > a and d > b
import sys
N = 5
# The function returns maximum value
# A(c,d) - A(a,b) over all choices of
# indexes such that both c > a and d > b.
def findMaxValue(mat):
# stores maximum value
maxValue = -sys.maxsize -1
# maxArr[i][j] stores max of elements
# in matrix from (i, j) to (N-1, N-1)
maxArr = [[0 for x in range(N)]
for y in range(N)]
# last element of maxArr will be
# same's as of the input matrix
maxArr[N - 1][N - 1] = mat[N - 1][N - 1]
# preprocess last row
maxv = mat[N - 1][N - 1]; # Initialize max
for j in range (N - 2, -1, -1):
if (mat[N - 1][j] > maxv):
maxv = mat[N - 1][j]
maxArr[N - 1][j] = maxv
# preprocess last column
maxv = mat[N - 1][N - 1] # Initialize max
for i in range (N - 2, -1, -1):
if (mat[i][N - 1] > maxv):
maxv = mat[i][N - 1]
maxArr[i][N - 1] = maxv
# preprocess rest of the matrix
# from bottom
for i in range (N - 2, -1, -1):
for j in range (N - 2, -1, -1):
# Update maxValue
if (maxArr[i + 1][j + 1] -
mat[i][j] > maxValue):
maxValue = (maxArr[i + 1][j + 1] -
mat[i][j])
# set maxArr (i, j)
maxArr[i][j] = max(mat[i][j],
max(maxArr[i][j + 1],
maxArr[i + 1][j]))
return maxValue
# Driver Code
mat = [[ 1, 2, -1, -4, -20 ],
[-8, -3, 4, 2, 1 ],
[ 3, 8, 6, 1, 3 ],
[ -4, -1, 1, 7, -6] ,
[0, -4, 10, -5, 1 ]]
print ("Maximum Value is",
findMaxValue(mat))
# This code is contributed by iAyushRaj
C#
// An efficient method to find
// maximum value of mat1[d]
// - ma[a][b] such that c > a
// and d > b
using System;
class GFG {
// The function returns
// maximum value A(c,d) - A(a,b)
// over all choices of indexes
// such that both c > a
// and d > b.
static int findMaxValue(int N, int [,]mat)
{
//stores maximum value
int maxValue = int.MinValue;
// maxArr[i][j] stores max
// of elements in matrix
// from (i, j) to (N-1, N-1)
int [,]maxArr = new int[N, N];
// last element of maxArr
// will be same's as of
// the input matrix
maxArr[N - 1, N - 1] = mat[N - 1,N - 1];
// preprocess last row
// Initialize max
int maxv = mat[N - 1, N - 1];
for (int j = N - 2; j >= 0; j--)
{
if (mat[N - 1, j] > maxv)
maxv = mat[N - 1, j];
maxArr[N - 1, j] = maxv;
}
// preprocess last column
// Initialize max
maxv = mat[N - 1,N - 1];
for (int i = N - 2; i >= 0; i--)
{
if (mat[i, N - 1] > maxv)
maxv = mat[i,N - 1];
maxArr[i,N - 1] = maxv;
}
// preprocess rest of the
// matrix from bottom
for (int i = N - 2; i >= 0; i--)
{
for (int j = N - 2; j >= 0; j--)
{
// Update maxValue
if (maxArr[i + 1,j + 1] -
mat[i, j] > maxValue)
maxValue = maxArr[i + 1,j + 1] -
mat[i, j];
// set maxArr (i, j)
maxArr[i,j] = Math.Max(mat[i, j],
Math.Max(maxArr[i, j + 1],
maxArr[i + 1, j]) );
}
}
return maxValue;
}
// Driver code
public static void Main ()
{
int N = 5;
int [,]mat = {{ 1, 2, -1, -4, -20 },
{ -8, -3, 4, 2, 1 },
{ 3, 8, 6, 1, 3 },
{ -4, -1, 1, 7, -6 },
{ 0, -4, 10, -5, 1 }};
Console.Write("Maximum Value is " +
findMaxValue(N,mat));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// An efficient method to find
// maximum value of mat[d] - ma[a][b]
// such that c > a and d > b
$N = 5;
// The function returns maximum
// value A(c,d) - A(a,b) over
// all choices of indexes such
// that both c > a and d > b.
function findMaxValue($mat)
{
global $N;
// stores maximum value
$maxValue = PHP_INT_MIN;
// maxArr[i][j] stores max
// of elements in matrix
// from (i, j) to (N-1, N-1)
$maxArr[$N][$N] = array();
// last element of maxArr
// will be same's as of
// the input matrix
$maxArr[$N - 1][$N - 1] = $mat[$N - 1][$N - 1];
// preprocess last row
$maxv = $mat[$N - 1][$N - 1]; // Initialize max
for ($j = $N - 2; $j >= 0; $j--)
{
if ($mat[$N - 1][$j] > $maxv)
$maxv = $mat[$N - 1][$j];
$maxArr[$N - 1][$j] = $maxv;
}
// preprocess last column
$maxv = $mat[$N - 1][$N - 1]; // Initialize max
for ($i = $N - 2; $i >= 0; $i--)
{
if ($mat[$i][$N - 1] > $maxv)
$maxv = $mat[$i][$N - 1];
$maxArr[$i][$N - 1] = $maxv;
}
// preprocess rest of the
// matrix from bottom
for ($i = $N - 2; $i >= 0; $i--)
{
for ($j = $N - 2; $j >= 0; $j--)
{
// Update maxValue
if ($maxArr[$i + 1][$j + 1] -
$mat[$i][$j] > $maxValue)
$maxValue = $maxArr[$i + 1][$j + 1] -
$mat[$i][$j];
// set maxArr (i, j)
$maxArr[$i][$j] = max($mat[$i][$j],
max($maxArr[$i][$j + 1],
$maxArr[$i + 1][$j]));
}
}
return $maxValue;
}
// Driver Code
$mat = array(array(1, 2, -1, -4, -20),
array(-8, -3, 4, 2, 1),
array(3, 8, 6, 1, 3),
array(-4, -1, 1, 7, -6),
array(0, -4, 10, -5, 1)
);
echo "Maximum Value is ".
findMaxValue($mat);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// An efficient method to find maximum value of mat1[d]
// - ma[a][b] such that c > a and d > b
// The function returns maximum value A(c,d) - A(a,b)
// over all choices of indexes such that both c > a
// and d > b.
function findMaxValue(N,mat)
{
// stores maximum value
let maxValue = Number.MIN_VALUE;
// maxArr[i][j] stores max of elements in matrix
// from (i, j) to (N-1, N-1)
let maxArr=new Array(N);
for(let i = 0; i < N; i++)
{
maxArr[i]=new Array(N);
}
// last element of maxArr will be same's as of
// the input matrix
maxArr[N - 1][N - 1] = mat[N - 1][N - 1];
// preprocess last row
let maxv = mat[N-1][N-1]; // Initialize max
for (let j = N - 2; j >= 0; j--)
{
if (mat[N - 1][j] > maxv)
maxv = mat[N - 1][j];
maxArr[N - 1][j] = maxv;
}
// preprocess last column
maxv = mat[N - 1][N - 1]; // Initialize max
for (let i = N - 2; i >= 0; i--)
{
if (mat[i][N - 1] > maxv)
maxv = mat[i][N - 1];
maxArr[i][N - 1] = maxv;
}
// preprocess rest of the matrix from bottom
for (let i = N-2; i >= 0; i--)
{
for (let j = N-2; j >= 0; j--)
{
// Update maxValue
if (maxArr[i+1][j+1] - mat[i][j] > maxValue)
maxValue = maxArr[i + 1][j + 1] - mat[i][j];
// set maxArr (i, j)
maxArr[i][j] = Math.max(mat[i][j],
Math.max(maxArr[i][j + 1],
maxArr[i + 1][j]) );
}
}
return maxValue;
}
// Driver code
let N = 5;
let mat = [[ 1, 2, -1, -4, -20 ],
[-8, -3, 4, 2, 1 ],
[ 3, 8, 6, 1, 3 ],
[ -4, -1, 1, 7, -6] ,
[0, -4, 10, -5, 1 ]];
document.write("Maximum Value is " +
findMaxValue(N,mat));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Maximum Value is 18
Complejidad temporal: O(N 2 ).
Espacio Auxiliar: O(N 2 )
Si se nos permite modificar la array, podemos evitar usar espacio adicional y usar la array de entrada en su lugar.
Ejercicio: Imprimir índice (a, b) y (c, d) también.
Este artículo es una contribución de Aarti_Rathi y Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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