Dadas tres arrays A[] , B[] y C[] de N enteros. Podemos elegir N elementos de esta array de modo que para cada índice i solo se pueda elegir un elemento de esta array, es decir, A[i] , B[i] o C[i], y no se pueden elegir dos elementos consecutivos de la misma array. La tarea es imprimir la suma máxima de números que podemos hacer eligiendo elementos de estas arrays.
Ejemplos:
Entrada: a[] = {10, 20, 30}, b[] = {40, 50, 60}, c[] = {70, 80, 90}
Salida: 210
70 + 50 + 90 = 210Entrada: a[] = {6, 8, 2, 7, 4, 2, 7}, b[] = {7, 8, 5, 8, 6, 3, 5}, c[] = {8, 3 , 2, 6, 8, 4, 1}
Salida: 46
Elija elementos de C, A, B, A, C, B y A.
Enfoque: El problema anterior se puede resolver usando Programación Dinámica . Sea dp[i][j] la suma máxima hasta i si se elige un elemento de la j-ésima array. Podemos seleccionar un elemento de cualquier array para el primer índice, pero más tarde recursivamente podemos elegir un elemento solo de las dos arrays restantes para el siguiente paso. La suma máxima devuelta por todas las combinaciones será nuestra respuesta. Utilice la memorización para evitar llamadas repetitivas y múltiples de la misma función.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int N = 3;
// Function to return the maximum sum
int FindMaximumSum(int ind, int kon, int a[], int b[],
int c[], int n, int dp[][N])
{
// Base case
if (ind == n)
return 0;
// Already visited
if (dp[ind][kon] != -1)
return dp[ind][kon];
int ans = -1e9 + 5;
// If the element has been taken
// from first array in previous step
if (kon == 0) {
ans = max(ans, b[ind] + FindMaximumSum(ind + 1,
1, a, b,
c, n, dp));
ans = max(ans, c[ind] + FindMaximumSum(ind + 1,
2, a, b,
c, n, dp));
}
// If the element has been taken
// from second array in previous step
else if (kon == 1) {
ans = max(ans, a[ind] + FindMaximumSum(ind + 1,
0, a, b,
c, n, dp));
ans = max(ans, c[ind] + FindMaximumSum(ind + 1,
2, a, b,
c, n, dp));
}
// If the element has been taken
// from third array in previous step
else if (kon == 2) {
ans = max(ans, a[ind] + FindMaximumSum(ind + 1,
1, a, b,
c, n, dp));
ans = max(ans, b[ind] + FindMaximumSum(ind + 1,
0, a, b,
c, n, dp));
}
return dp[ind][kon] = ans;
}
// Driver code
int main()
{
int a[] = { 6, 8, 2, 7, 4, 2, 7 };
int b[] = { 7, 8, 5, 8, 6, 3, 5 };
int c[] = { 8, 3, 2, 6, 8, 4, 1 };
int n = sizeof(a) / sizeof(a[0]);
int dp[n][N];
memset(dp, -1, sizeof dp);
// Pick element from first array
int x = FindMaximumSum(0, 0, a, b, c, n, dp);
// Pick element from second array
int y = FindMaximumSum(0, 1, a, b, c, n, dp);
// Pick element from third array
int z = FindMaximumSum(0, 2, a, b, c, n, dp);
// Print the maximum of them
cout << max(x, max(y, z));
return 0;
}
Java
// Java program for the above approach
class GFG {
static int N = 3;
// Function to return the maximum sum
static int FindMaximumSum(int ind, int kon, int a[],
int b[], int c[], int n, int dp[][])
{
// Base case
if (ind == n)
return 0;
// Already visited
if (dp[ind][kon] != -1)
return dp[ind][kon];
int ans = (int) (-1e9 + 5);
// If the element has been taken
// from first array in previous step
if (kon == 0) {
ans = Math.max(ans, b[ind] +
FindMaximumSum(ind + 1,
1, a, b,c, n, dp));
ans = Math.max(ans, c[ind] +
FindMaximumSum(ind + 1,
2, a, b,c, n, dp));
}
// If the element has been taken
// from second array in previous step
else if (kon == 1) {
ans = Math.max(ans, a[ind] +
FindMaximumSum(ind + 1,
0, a, b, c, n, dp));
ans = Math.max(ans, c[ind] +
FindMaximumSum(ind + 1,
2, a, b, c, n, dp));
}
// If the element has been taken
// from third array in previous step
else if (kon == 2) {
ans = Math.max(ans, a[ind] +
FindMaximumSum(ind + 1,
1, a, b, c, n, dp));
ans = Math.max(ans, b[ind] +
FindMaximumSum(ind + 1,
0, a, b, c, n, dp));
}
return dp[ind][kon] = ans;
}
// Driver code
public static void main(String[] args) {
int a[] = { 6, 8, 2, 7, 4, 2, 7 };
int b[] = { 7, 8, 5, 8, 6, 3, 5 };
int c[] = { 8, 3, 2, 6, 8, 4, 1 };
int n = a.length;
int dp[][] = new int[n][N];
for(int i = 0; i < n; i++) {
for(int j = 0; j < N; j++) {
dp[i][j] =- 1;
}
}
// Pick element from first array
int x = FindMaximumSum(0, 0, a, b, c, n, dp);
// Pick element from second array
int y = FindMaximumSum(0, 1, a, b, c, n, dp);
// Pick element from third array
int z = FindMaximumSum(0, 2, a, b, c, n, dp);
// Print the maximum of them
System.out.println(Math.max(x, Math.max(y, z)));
}
}
// This code has been contributed
// by 29AjayKumar
Python3
# Python3 implementation of the approach # Function to return the maximum sum def FindMaximumSum(ind, kon, a, b, c, n, dp): # Base case if ind == n: return 0 # Already visited if dp[ind][kon] != -1: return dp[ind][kon] ans = -10 ** 9 + 5 # If the element has been taken # from first array in previous step if kon == 0: ans = max(ans, b[ind] + FindMaximumSum(ind + 1, 1, a, b, c, n, dp)) ans = max(ans, c[ind] + FindMaximumSum(ind + 1, 2, a, b, c, n, dp)) # If the element has been taken # from second array in previous step elif kon == 1: ans = max(ans, a[ind] + FindMaximumSum(ind + 1, 0, a, b, c, n, dp)) ans = max(ans, c[ind] + FindMaximumSum(ind + 1, 2, a, b, c, n, dp)) # If the element has been taken # from third array in previous step elif kon == 2: ans = max(ans, a[ind] + FindMaximumSum(ind + 1, 1, a, b, c, n, dp)) ans = max(ans, b[ind] + FindMaximumSum(ind + 1, 0, a, b, c, n, dp)) dp[ind][kon] = ans return ans # Driver code if __name__ == "__main__": N = 3 a = [6, 8, 2, 7, 4, 2, 7] b = [7, 8, 5, 8, 6, 3, 5] c = [8, 3, 2, 6, 8, 4, 1] n = len(a) dp = [[-1 for i in range(N)] for j in range(n)] # Pick element from first array x = FindMaximumSum(0, 0, a, b, c, n, dp) # Pick element from second array y = FindMaximumSum(0, 1, a, b, c, n, dp) # Pick element from third array z = FindMaximumSum(0, 2, a, b, c, n, dp) # Print the maximum of them print(max(x, y, z)) # This code is contributed # by Rituraj Jain
C#
// C# program for the above approach
using System;
class GFG
{
static int N = 3;
// Function to return the maximum sum
static int FindMaximumSum(int ind, int kon, int []a,
int []b, int []c, int n, int [,]dp)
{
// Base case
if (ind == n)
return 0;
// Already visited
if (dp[ind,kon] != -1)
return dp[ind,kon];
int ans = (int) (-1e9 + 5);
// If the element has been taken
// from first array in previous step
if (kon == 0)
{
ans = Math.Max(ans, b[ind] +
FindMaximumSum(ind + 1,
1, a, b,c, n, dp));
ans = Math.Max(ans, c[ind] +
FindMaximumSum(ind + 1,
2, a, b,c, n, dp));
}
// If the element has been taken
// from second array in previous step
else if (kon == 1)
{
ans = Math.Max(ans, a[ind] +
FindMaximumSum(ind + 1,
0, a, b, c, n, dp));
ans = Math.Max(ans, c[ind] +
FindMaximumSum(ind + 1,
2, a, b, c, n, dp));
}
// If the element has been taken
// from third array in previous step
else if (kon == 2)
{
ans = Math.Max(ans, a[ind] +
FindMaximumSum(ind + 1,
1, a, b, c, n, dp));
ans = Math.Max(ans, b[ind] +
FindMaximumSum(ind + 1,
0, a, b, c, n, dp));
}
return dp[ind,kon] = ans;
}
// Driver code
public static void Main()
{
int []a = { 6, 8, 2, 7, 4, 2, 7 };
int []b = { 7, 8, 5, 8, 6, 3, 5 };
int []c = { 8, 3, 2, 6, 8, 4, 1 };
int n = a.Length;
int [,]dp = new int[n,N];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < N; j++)
{
dp[i,j] =- 1;
}
}
// Pick element from first array
int x = FindMaximumSum(0, 0, a, b, c, n, dp);
// Pick element from second array
int y = FindMaximumSum(0, 1, a, b, c, n, dp);
// Pick element from third array
int z = FindMaximumSum(0, 2, a, b, c, n, dp);
// Print the maximum of them
Console.WriteLine(Math.Max(x, Math.Max(y, z)));
}
}
// This code has been contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
$N = 3;
// Function to return the maximum sum
function FindMaximumSum($ind, $kon, $a,
$b, $c, $n, $dp)
{
global $N;
// Base case
if ($ind == $n)
return 0;
// Already visited
if ($dp[$ind][$kon] != -1)
return $dp[$ind][$kon];
$ans = -1e9 + 5;
// If the element has been taken
// from first array in previous step
if ($kon == 0)
{
$ans = max($ans, $b[$ind] +
FindMaximumSum($ind + 1, 1, $a,
$b, $c, $n, $dp));
$ans = max($ans, $c[$ind] +
FindMaximumSum($ind + 1, 2, $a,
$b, $c, $n, $dp));
}
// If the element has been taken
// from second array in previous step
else if ($kon == 1)
{
$ans = max($ans, $a[$ind] +
FindMaximumSum($ind + 1, 0,
$a, $b, $c, $n, $dp));
$ans = max($ans, $c[$ind] +
FindMaximumSum($ind + 1, 2,
$a, $b, $c, $n, $dp));
}
// If the element has been taken
// from third array in previous step
else if ($kon == 2)
{
$ans = max($ans, $a[$ind] +
FindMaximumSum($ind + 1, 1,
$a, $b, $c, $n, $dp));
$ans = max($ans, $b[$ind] +
FindMaximumSum($ind + 1, 0,
$a, $b, $c, $n, $dp));
}
return $dp[$ind][$kon] = $ans;
}
// Driver code
$a = array( 6, 8, 2, 7, 4, 2, 7 );
$b = array( 7, 8, 5, 8, 6, 3, 5 );
$c = array( 8, 3, 2, 6, 8, 4, 1 );
$n = count($a);
$dp = array_fill(0, $n,
array_fill(0, $N, -1));
// Pick element from first array
$x = FindMaximumSum(0, 0, $a, $b,
$c, $n, $dp);
// Pick element from second array
$y = FindMaximumSum(0, 1, $a, $b,
$c, $n, $dp);
// Pick element from third array
$z = FindMaximumSum(0, 2, $a, $b,
$c, $n, $dp);
// Print the maximum of them
print(max($x, max($y, $z)));
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript implementation of the approach
var N = 3;
// Function to return the maximum sum
function FindMaximumSum(ind, kon, a, b, c, n, dp)
{
// Base case
if (ind == n)
return 0;
// Already visited
if (dp[ind][kon] != -1)
return dp[ind][kon];
var ans = -1000000005;
// If the element has been taken
// from first array in previous step
if (kon == 0) {
ans = Math.max(ans, b[ind] + FindMaximumSum(ind + 1,
1, a, b,
c, n, dp));
ans = Math.max(ans, c[ind] + FindMaximumSum(ind + 1,
2, a, b,
c, n, dp));
}
// If the element has been taken
// from second array in previous step
else if (kon == 1) {
ans = Math.max(ans, a[ind] + FindMaximumSum(ind + 1,
0, a, b,
c, n, dp));
ans = Math.max(ans, c[ind] + FindMaximumSum(ind + 1,
2, a, b,
c, n, dp));
}
// If the element has been taken
// from third array in previous step
else if (kon == 2) {
ans = Math.max(ans, a[ind] + FindMaximumSum(ind + 1,
1, a, b,
c, n, dp));
ans = Math.max(ans, b[ind] + FindMaximumSum(ind + 1,
0, a, b,
c, n, dp));
}
return dp[ind][kon] = ans;
}
// Driver code
var a = [ 6, 8, 2, 7, 4, 2, 7 ];
var b = [ 7, 8, 5, 8, 6, 3, 5 ];
var c = [ 8, 3, 2, 6, 8, 4, 1 ];
var n = a.length;
var dp = Array.from(Array(n), ()=> Array(n).fill(-1));
// Pick element from first array
var x = FindMaximumSum(0, 0, a, b, c, n, dp);
// Pick element from second array
var y = FindMaximumSum(0, 1, a, b, c, n, dp);
// Pick element from third array
var z = FindMaximumSum(0, 2, a, b, c, n, dp);
// Print the maximum of them
document.write( Math.max(x, Math.max(y, z)));
</script>
Producción:
45
Complejidad de tiempo: O(N), como estamos usando recursividad con memorización evitaremos las llamadas a funciones redundantes. Donde N es el número de elementos de la array.
Espacio auxiliar: O(N), ya que estamos usando espacio extra para la array dp. Donde N es el número de elementos de la array.