Dadas dos arrays arr1[] y arr2[] de igual longitud, la tarea es encontrar la suma máxima de cualquier subconjunto posible seleccionando elementos de ambas arrays de modo que no haya dos elementos en el subconjunto que sean consecutivos.
Ejemplos:
Entrada: arr1[] = {-1, -2, 4, -4, 5}, arr2[] = {-1, -2, -3, 4, 10}
Salida: 14
Explicación:
Subconjunto requerido {4, 10 }. Por lo tanto, suma = 4 + 10 = 14.Entrada: arr1[] = {2, 5, 4, 2000}, arr2[] = {-2000, 100, 23, 40}
Salida: 2100
Enfoque ingenuo: el enfoque más simple es generar todos los subconjuntos posibles a partir de las arrays dadas de modo que no haya dos elementos adyacentes consecutivos y calcular la suma de cada subconjunto. Finalmente, imprima la suma máxima posible.
Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(2 N )
Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica . Siga los pasos a continuación para resolver el problema:
- Inicialice una array auxiliar dp[] de tamaño N .
- Aquí, dp[i] almacena la suma máxima posible de un subconjunto de ambas arrays de modo que no haya dos elementos consecutivos.
- Declare una función maximumSubsetSum():
- Casos básicos:
- dp[1] = max(arr1[1], arr2[1]).
- dp[2] = max(max(arr1[1], arr2[1]), max(arr1[2], arr2[2])).
- Para todos los demás casos, se dan las siguientes tres condiciones:
- dp[i] = max(arr1[i], arr2[i], arr1[i] + dp[i – 2], arr2[i] + dp[i – 2], dp[i – 1]).
- Casos básicos:
- Finalmente, imprima dp[N] como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate maximum subset sum
void maximumSubsetSum(int arr1[],int arr2[], int length)
{
// Initialize array to store dp states
int dp[length+1];
// Base Cases
if (length == 1)
{
cout << (max(arr1[0], arr2[0]));
return;
}
if (length == 2)
{
cout << (max(max(arr1[1], arr2[1]), max(arr1[0], arr2[0])));
return;
}
else
{
// Pre initializing for dp[0] & dp[1]
dp[0] = max(arr1[0], arr2[0]);
dp[1] = max(max(arr1[1], arr2[1]), max(arr1[0], arr2[0]));
int index = 2;
while (index < length)
{
// Calculating dp[index] based on
// above formula
dp[index] = max(max(arr1[index], arr2[index]),
max(max(arr1[index] + dp[index - 2],
arr2[index] + dp[index - 2]),
dp[index - 1]));
++index;
}
// Print maximum subset sum
cout<<(dp[length - 1]);
}
}
// Driver Code
int main()
{
// Given arrays
int arr1[] = { -1, -2, 4, -4, 5 };
int arr2[] = { -1, -2, -3, 4, 10 };
// Length of the array
int length = 5;
maximumSubsetSum(arr1, arr2, length);
return 0;
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to calculate maximum subset sum
static void maximumSubsetSum(int arr1[],
int arr2[],
int length)
{
// Initialize array to store dp states
int dp[] = new int[length + 1];
// Base Cases
if (length == 1) {
System.out.print(
Math.max(arr1[0], arr2[0]));
return;
}
if (length == 2) {
System.out.print(
Math.max(
Math.max(arr1[1], arr2[1]),
Math.max(arr1[0], arr2[0])));
return;
}
else {
// Pre initializing for dp[0] & dp[1]
dp[0] = Math.max(arr1[0], arr2[0]);
dp[1] = Math.max(
Math.max(arr1[1], arr2[1]),
Math.max(arr1[0], arr2[0]));
int index = 2;
while (index < length) {
// Calculating dp[index] based on
// above formula
dp[index] = Math.max(
Math.max(arr1[index], arr2[index]),
Math.max(
Math.max(
arr1[index] + dp[index - 2],
arr2[index] + dp[index - 2]),
dp[index - 1]));
++index;
}
// Print maximum subset sum
System.out.print(dp[length - 1]);
}
}
// Driver Code
public static void main(String[] args)
{
// Given arrays
int arr1[] = { -1, -2, 4, -4, 5 };
int arr2[] = { -1, -2, -3, 4, 10 };
// Length of the array
int length = arr1.length;
maximumSubsetSum(arr1, arr2, length);
}
}
Python3
# Python program of the above approach # Function to calculate maximum subset sum def maximumSubsetSum(arr1, arr2, length) : # Initialize array to store dp states dp = [0] * (length+1) # Base Cases if (length == 1) : print(max(arr1[0], arr2[0])) return if (length == 2) : print(max(max(arr1[1], arr2[1]), max(arr1[0], arr2[0]))) return else : # Pre initializing for dp[0] & dp[1] dp[0] = max(arr1[0], arr2[0]) dp[1] = max(max(arr1[1], arr2[1]), max(arr1[0], arr2[0])) index = 2 while (index < length) : # Calculating dp[index] based on # above formula dp[index] = max(max(arr1[index], arr2[index]), max(max(arr1[index] + dp[index - 2], arr2[index] + dp[index - 2]), dp[index - 1])) index += 1 # Print maximum subset sum print(dp[length - 1]) # Driver Code # Given arrays arr1 = [ -1, -2, 4, -4, 5 ] arr2 = [ -1, -2, -3, 4, 10 ] # Length of the array length = 5 maximumSubsetSum(arr1, arr2, length) # This code is contributed by susmitakundugoaldanga.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to calculate maximum subset sum
static void maximumSubsetSum(int[] arr1,
int[] arr2,
int length)
{
// Initialize array to store dp states
int[] dp = new int[length + 1];
// Base Cases
if (length == 1) {
Console.WriteLine(Math.Max(arr1[0], arr2[0]));
return;
}
if (length == 2)
{
Console.WriteLine(Math.Max(
Math.Max(arr1[1], arr2[1]),
Math.Max(arr1[0], arr2[0])));
return;
}
else
{
// Pre initializing for dp[0] & dp[1]
dp[0] = Math.Max(arr1[0], arr2[0]);
dp[1] = Math.Max(Math.Max(arr1[1], arr2[1]),
Math.Max(arr1[0], arr2[0]));
int index = 2;
while (index < length) {
// Calculating dp[index] based on
// above formula
dp[index] = Math.Max(Math.Max(arr1[index], arr2[index]),
Math.Max(Math.Max(arr1[index] +
dp[index - 2],
arr2[index] +
dp[index - 2]),
dp[index - 1]));
++index;
}
// Print maximum subset sum
Console.WriteLine(dp[length - 1]);
}
}
// Driver Code
static public void Main()
{
// Given arrays
int[] arr1 = { -1, -2, 4, -4, 5 };
int[] arr2 = { -1, -2, -3, 4, 10 };
// Length of the array
int length = arr1.Length;
maximumSubsetSum(arr1, arr2, length);
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// javascript program of the above approach
// Function to calculate maximum subset sum
function maximumSubsetSum(arr1, arr2,length)
{
// Initialize array to store dp states
let dp = new Array(length).fill(0);;
// Base Cases
if (length == 1) {
document.write(
Math.max(arr1[0], arr2[0]));
return;
}
if (length == 2) {
document.write(
Math.max(
Math.max(arr1[1], arr2[1]),
Math.max(arr1[0], arr2[0])));
return;
}
else {
// Pre initializing for dp[0] & dp[1]
dp[0] = Math.max(arr1[0], arr2[0]);
dp[1] = Math.max(
Math.max(arr1[1], arr2[1]),
Math.max(arr1[0], arr2[0]));
let index = 2;
while (index < length) {
// Calculating dp[index] based on
// above formula
dp[index] = Math.max(
Math.max(arr1[index], arr2[index]),
Math.max(
Math.max(
arr1[index] + dp[index - 2],
arr2[index] + dp[index - 2]),
dp[index - 1]));
++index;
}
// Print maximum subset sum
document.write(dp[length - 1]);
}
}
// Driver Code
// Given arrays
let arr1 = [ -1, -2, 4, -4, 5 ];
let arr2 = [ -1, -2, -3, 4, 10 ];
// Length of the array
let length = arr1.length;
maximumSubsetSum(arr1, arr2, length);
</script>
Producción:
14
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA