Dadas n arrays de tamaño m cada una. Encuentre la suma máxima obtenida al seleccionar un número de cada array de modo que los elementos seleccionados de la i-ésima array sean más que el elemento seleccionado de (i-1)-ésima array. Si no se puede obtener la suma máxima, devuelva 0.
Ejemplos:
Input : arr[][] = {{1, 7, 3, 4},
{4, 2, 5, 1},
{9, 5, 1, 8}}
Output : 18
Explanation :
We can select 4 from first array, 5 from
second array and 9 from third array.
Input : arr[][] = {{9, 8, 7},
{6, 5, 4},
{3, 2, 1}}
Output : 0
La idea es comenzar a elegir desde la última array. Elegimos el elemento máximo de la última array, luego nos movemos a la penúltima array. En la penúltima array, encontramos el elemento más grande que es más pequeño que el elemento máximo seleccionado de la última array. Repetimos este proceso hasta llegar a la primera array.
Para obtener la suma máxima, podemos ordenar todas las arrays y comenzar de abajo hacia arriba recorriendo cada array de derecha a izquierda y elegir un número tal que sea mayor que el elemento anterior. Si no podemos seleccionar un elemento de la array, devuelva 0.
C++
// CPP program to find maximum sum
// by selecting a element from n arrays
#include <bits/stdc++.h>
#define M 4
using namespace std;
// To calculate maximum sum by
// selecting element from each array
int maximumSum(int a[][M], int n) {
// Sort each array
for (int i = 0; i < n; i++)
sort(a[i], a[i] + M);
// Store maximum element
// of last array
int sum = a[n - 1][M - 1];
int prev = a[n - 1][M - 1];
int i, j;
// Selecting maximum element from
// previously selected element
for (i = n - 2; i >= 0; i--) {
for (j = M - 1; j >= 0; j--) {
if (a[i][j] < prev) {
prev = a[i][j];
sum += prev;
break;
}
}
// j = -1 means no element is
// found in a[i] so return 0
if (j == -1)
return 0;
}
return sum;
}
// Driver program to test maximumSum
int main() {
int arr[][M] = {{1, 7, 3, 4},
{4, 2, 5, 1},
{9, 5, 1, 8}};
int n = sizeof(arr) / sizeof(arr[0]);
cout << maximumSum(arr, n);
return 0;
}
Java
// Java program to find
// maximum sum by selecting
// a element from n arrays
import java.io.*;
class GFG
{
static int M = 4;
static int arr[][] = {{1, 7, 3, 4},
{4, 2, 5, 1},
{9, 5, 1, 8}};
static void sort(int a[][],
int row, int n)
{
for (int i = 0; i < M - 1; i++)
{
if(a[row][i] > a[row][i + 1])
{
int temp = a[row][i];
a[row][i] = a[row][i + 1];
a[row][i + 1] = temp;
}
}
}
// To calculate maximum
// sum by selecting element
// from each array
static int maximumSum(int a[][],
int n)
{
// Sort each array
for (int i = 0; i < n; i++)
sort(a, i, n);
// Store maximum element
// of last array
int sum = a[n - 1][M - 1];
int prev = a[n - 1][M - 1];
int i, j;
// Selecting maximum element
// from previously selected
// element
for (i = n - 2; i >= 0; i--)
{
for (j = M - 1; j >= 0; j--)
{
if (a[i][j] < prev)
{
prev = a[i][j];
sum += prev;
break;
}
}
// j = -1 means no element
// is found in a[i] so
// return 0
if (j == -1)
return 0;
}
return sum;
}
// Driver Code
public static void main(String args[])
{
int n = arr.length;
System.out.print(maximumSum(arr, n));
}
}
// This code is contributed by
// Manish Shaw(manishshaw1)
Python3
# Python3 program to find # maximum sum by selecting # a element from n arrays M = 4; # To calculate maximum sum # by selecting element from # each array def maximumSum(a, n) : global M; # Sort each array for i in range(0, n) : a[i].sort(); # Store maximum element # of last array sum = a[n - 1][M - 1]; prev = a[n - 1][M - 1]; # Selecting maximum # element from previously # selected element for i in range(n - 2, -1, -1) : for j in range(M - 1, -1, -1) : if (a[i][j] < prev) : prev = a[i][j]; sum += prev; break; # j = -1 means no element # is found in a[i] so # return 0 if (j == -1) : return 0; return sum; # Driver Code arr = [[1, 7, 3, 4], [4, 2, 5, 1], [9, 5, 1, 8]]; n = len(arr) ; print (maximumSum(arr, n)); # This code is contributed by # Manish Shaw(manishshaw1)
C#
// C# program to find maximum
// sum by selecting a element
// from n arrays
using System;
class GFG
{
static int M = 4;
static void sort(ref int[,] a,
int row, int n)
{
for (int i = 0; i < M-1; i++)
{
if(a[row, i] > a[row, i + 1])
{
int temp = a[row, i];
a[row, i] = a[row, i + 1];
a[row, i + 1] = temp;
}
}
}
// To calculate maximum
// sum by selecting
// element from each array
static int maximumSum(int[,] a,
int n)
{
int i = 0, j = 0;
// Sort each array
for (i = 0; i < n; i++)
sort(ref a, i, n);
// Store maximum element
// of last array
int sum = a[n - 1, M - 1];
int prev = a[n - 1, M - 1];
// Selecting maximum element
// from previously selected
// element
for (i = n - 2; i >= 0; i--)
{
for (j = M - 1; j >= 0; j--)
{
if (a[i, j] < prev)
{
prev = a[i, j];
sum += prev;
break;
}
}
// j = -1 means no element
// is found in a[i] so
// return 0
if (j == -1)
return 0;
}
return sum;
}
// Driver Code
static void Main()
{
int [,]arr = new int[,]{{1, 7, 3, 4},
{4, 2, 5, 1},
{9, 5, 1, 8}};
int n = arr.GetLength(0);
Console.Write(maximumSum(arr, n));
}
}
// This code is contributed by
// Manish Shaw (manishshaw1)
PHP
<?php
// PHP program to find maximum
// sum by selecting a element
// from n arrays
$M = 4;
// To calculate maximum sum
// by selecting element from
// each array
function maximumSum($a, $n)
{
global $M;
// Sort each array
for ($i = 0; $i < $n; $i++)
sort($a[$i]);
// Store maximum element
// of last array
$sum = $a[$n - 1][$M - 1];
$prev = $a[$n - 1][$M - 1];
$i; $j;
// Selecting maximum element from
// previously selected element
for ($i = $n - 2; $i >= 0; $i--)
{
for ($j = $M - 1; $j >= 0; $j--)
{
if ($a[$i][$j] < $prev)
{
$prev = $a[$i][$j];
$sum += $prev;
break;
}
}
// j = -1 means no element is
// found in a[i] so return 0
if ($j == -1)
return 0;
}
return $sum;
}
// Driver Code
$arr = array(array(1, 7, 3, 4),
array(4, 2, 5, 1),
array(9, 5, 1, 8));
$n = sizeof($arr) ;
echo maximumSum($arr, $n);
// This code is contributed by m_kit
?>
Javascript
<script>
// JavaScript program to find
// maximum sum by selecting
// a element from n arrays
let M = 4;
// To calculate maximum sum
// by selecting element from
// each array
function maximumSum(a, n)
{
// Store maximum element
// of last array
let prev = Math.max(a[n - 1][0],
a[n - 1][M - 1] + 1);
// Selecting maximum element from
// previously selected element
let sum = prev;
for (let i = n - 2; i >= 0; i--)
{
let max_smaller = Number.MIN_VALUE;
for (let j = M - 1; j >= 0; j--)
{
if (a[i][j] < prev &&
a[i][j] > max_smaller)
max_smaller = a[i][j];
}
// max_smaller equals to
// INT_MIN means no element
// is found in a[i] so return 0
if (max_smaller == Number.MIN_VALUE)
return 0;
prev = max_smaller;
sum += max_smaller;
}
return sum;
}
// Driver code
let arr = [[1, 7, 3, 4],
[4, 2, 5, 1],
[9, 5, 1, 8]];
let n = arr.length;
document.write(maximumSum(arr, n));
</script>
Producción:
18
La complejidad del tiempo en el peor de los casos: O(mn Log m)
Podemos optimizar la solución anterior para trabajar en O(mn). Podemos omitir la clasificación para encontrar el máximo de elementos.
C++
// CPP program to find maximum sum by selecting a element
// from n arrays
#include <bits/stdc++.h>
#define M 4
using namespace std;
// To calculate maximum sum by selecting element from each
// array
int maximumSum(int a[][M], int n)
{
// Store maximum element of last array
int prev
= *max_element(&a[n - 1][0], &a[n - 1][M - 1] + 1);
// Selecting maximum element from previously selected
// element
int sum = prev;
for (int i = n - 2; i >= 0; i--) {
int max_smaller = INT_MIN;
for (int j = M - 1; j >= 0; j--)
if (a[i][j] < prev && a[i][j] > max_smaller)
max_smaller = a[i][j];
// max_smaller equals to INT_MIN means no element is
// found in a[i] so return 0
if (max_smaller == INT_MIN)
return 0;
prev = max_smaller;
sum += max_smaller;
}
return sum;
}
// Driver program to test maximumSum
int main()
{
int arr[][M] = { { 1, 7, 3, 4 },
{ 4, 2, 5, 1 },
{ 9, 5, 1, 8 } };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maximumSum(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to find maximum sum by selecting a element from
// n arrays
#include <limits.h>
#include <stdio.h>
#define M 4
// To calculate maximum sum by selecting element from each
// array
int maximumSum(int a[][M], int n)
{
// Store maximum element of last array
int prev = INT_MAX;
// Selecting maximum element from previously selected
// element
int sum = 0;
for (int i = n - 1; i >= 0; i--) {
int max_smaller = INT_MIN;
for (int j = 0; j < M; j++)
if (a[i][j] > max_smaller && a[i][j] < prev)
max_smaller = a[i][j];
// max_smaller equals to INT_MIN means no element is
// found in a[i] so return 0
if (max_smaller == INT_MIN)
return 0;
prev = max_smaller;
sum += max_smaller;
}
return sum;
}
// Driver program to test maximumSum
int main()
{
int arr[][M] = { { 1, 7, 3, 4 },
{ 4, 2, 5, 1 },
{ 9, 5, 1, 8 } };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", maximumSum(arr, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to find maximum sum by selecting a element
// from n arrays
import java.util.*;
class GFG {
static int M = 4;
// To calculate maximum sum by selecting element from
// each array
static int maximumSum(int a[][], int n)
{
// Store maximum element of last array
int prev
= Math.max(a[n - 1][0], a[n - 1][M - 1] + 1);
// Selecting maximum element from previously
// selected element
int sum = prev;
for (int i = n - 2; i >= 0; i--) {
int max_smaller = Integer.MIN_VALUE;
for (int j = M - 1; j >= 0; j--)
if (a[i][j] < prev && a[i][j] > max_smaller)
max_smaller = a[i][j];
// max_smaller equals to INT_MIN means no
// element is found in a[i] so return 0
if (max_smaller == Integer.MIN_VALUE)
return 0;
prev = max_smaller;
sum += max_smaller;
}
return sum;
}
// Driver code
public static void main(String[] args)
{
int arr[][] = { { 1, 7, 3, 4 },
{ 4, 2, 5, 1 },
{ 9, 5, 1, 8 } };
int n = arr.length;
System.out.print(maximumSum(arr, n));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# Python3 program to find maximum sum # by selecting a element from n arrays M = 4 # To calculate maximum sum by # selecting element from each array def maximumSum(a, n): # Store maximum element of last array prev = max(max(a)) # Selecting maximum element from # previously selected element Sum = prev for i in range(n - 2, -1, -1): max_smaller = -10**9 for j in range(M - 1, -1, -1): if (a[i][j] < prev and a[i][j] > max_smaller): max_smaller = a[i][j] # max_smaller equals to INT_MIN means # no element is found in a[i] so # return 0 if (max_smaller == -10**9): return 0 prev = max_smaller Sum += max_smaller return Sum # Driver Code arr = [[1, 7, 3, 4], [4, 2, 5, 1], [9, 5, 1, 8]] n = len(arr) print(maximumSum(arr, n)) # This code is contributed by mohit kumar
C#
// C# program to find
// maximum sum by selecting
// a element from n arrays
using System;
class GFG
{
static int M = 4;
// To calculate maximum sum
// by selecting element from
// each array
static int maximumSum(int[,] a, int n)
{
// Store maximum element
// of last array
int prev = Math.Max(a[n - 1, 0],
a[n - 1, M - 1] + 1);
// Selecting maximum element from
// previously selected element
int sum = prev;
for(int i = n - 2; i >= 0; i--)
{
int max_smaller = Int32.MinValue;
for(int j = M - 1; j >= 0; j--)
{
if(a[i, j] < prev && a[i, j] > max_smaller)
{
max_smaller = a[i, j];
}
}
// max_smaller equals to
// INT_MIN means no element
// is found in a[i] so return 0
if(max_smaller == Int32.MinValue)
{
return 0;
}
prev = max_smaller;
sum += max_smaller;
}
return sum;
}
// Driver code
static public void Main ()
{
int[,] arr = {{1, 7, 3, 4},{4, 2, 5, 1},{9, 5, 1, 8}};
int n = arr.GetLength(0);
Console.Write(maximumSum(arr, n));
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// JavaScript program to find
// maximum sum by selecting
// a element from n arrays
let M = 4;
// To calculate maximum sum
// by selecting element from
// each array
function maximumSum(a, n)
{
// Store maximum element
// of last array
let prev = Math.max(a[n - 1][0],
a[n - 1][M - 1] + 1);
// Selecting maximum element from
// previously selected element
let sum = prev;
for (let i = n - 2; i >= 0; i--)
{
let max_smaller = Number.MIN_VALUE;
for (let j = M - 1; j >= 0; j--)
{
if (a[i][j] < prev &&
a[i][j] > max_smaller)
max_smaller = a[i][j];
}
// max_smaller equals to
// INT_MIN means no element
// is found in a[i] so return 0
if (max_smaller == Number.MIN_VALUE)
return 0;
prev = max_smaller;
sum += max_smaller;
}
return sum;
}
// Driver code
let arr = [[1, 7, 3, 4],
[4, 2, 5, 1],
[9, 5, 1, 8]];
let n = arr.length;
document.write(maximumSum(arr, n));
// This code is contributed by souravghosh0416.
</script>
Producción:
18
Complejidad de tiempo: O(mn)