Dada una array arr[] de tamaño N , la tarea es encontrar la suma máxima posible de un subconjunto de la array tal que no haya dos elementos consecutivos que formen parte del subconjunto.
Ejemplos :
Entrada: arr[] = {2, 3, 2, 3, 3, 4}
Salida: 9
Explicación: El subconjunto que tiene todos los 3, es decir, {3, 3, 3} tiene suma = 9.
Esta es la suma máxima posible de cualquier subconjunto posible de la array que sigue a la condición.Entrada: arr[] = {2, 3, 4}
Salida: 6
Explicación: El subconjunto es {2, 4}. Tiene suma = 6 que es el máximo posible.
Enfoque ingenuo : el enfoque ingenuo es generar todos los subconjuntos posibles y, a partir de ellos, verificar qué subconjuntos siguen la condición dada. Calcula la suma de esos subconjuntos y el máximo entre ellos es la respuesta requerida.
Complejidad de Tiempo: O(2 N )
Espacio Auxiliar: O(2 N )
Enfoque eficiente: un enfoque eficiente es utilizar la programación dinámica con la ayuda de la siguiente idea:
Para cualquier elemento X en arr[], el valor X-1 no puede ser considerado pero todos los elementos que tienen valor X pueden serlo. Entonces, para X, la máxima respuesta posible hasta X es máxima entre (máxima respuesta posible hasta X-2 + freq(X)*X) y (máxima respuesta posible hasta X-1)
Siga los pasos que se mencionan a continuación para resolver el problema:
- Utilice hashing para almacenar la frecuencia de cada elemento.
- Encuentre el valor máximo de la array. (decir X )
- Cree una array dp[] donde dp[i] almacene la suma máxima posible del subconjunto cuando los elementos con valor como máximo i estén incluidos en el subconjunto.
- Iterar de i = 2 a X de la array:
- Calcule el valor de dp[i] según la fórmula de la observación dp[i] = max(dp[i-2] + i*freq(i), dp[i-1]) .
- El valor máximo de la array dp[] es la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the maximum value
int MaximiseStockPurchase(vector<int>& nums,
int n)
{
int maxi = 0;
for (int i = 0; i < n; i++)
maxi = max(maxi, nums[i]);
vector<int> freq(maxi + 1, 0);
vector<int> dp(maxi + 1, 0);
for (auto i : nums)
freq[i]++;
dp[1] = freq[1];
// Loop to calculate dp[] array
// till max element of array
for (int i = 2; i <= maxi; i++)
dp[i] = max(dp[i - 2] + i * freq[i],
dp[i - 1]);
return dp[maxi];
}
// Driver code
int main()
{
vector<int> arr{ 2, 2, 3, 4, 3, 3 };
int N = arr.size();
int res = MaximiseStockPurchase(arr, N);
cout << res;
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
class GFG {
// Function to calculate the maximum value
static int MaximiseStockPurchase(int nums[],
int n)
{
int maxi = 0;
for (int i = 0; i < n; i++)
maxi = Math.max(maxi, nums[i]);
int freq[] = new int[maxi + 1];
int dp[] = new int[maxi + 1];
for (int i = 0; i < n; i++)
freq[nums[i]]++;
dp[1] = freq[1];
// Loop to calculate dp[] array
// till max element of array
for (int i = 2; i <= maxi; i++)
dp[i] = Math.max(dp[i - 2] + i * freq[i],
dp[i - 1]);
return dp[maxi];
}
// Driver code
public static void main (String[] args) {
int arr[] = { 2, 2, 3, 4, 3, 3 };
int N = arr.length;
int res = MaximiseStockPurchase(arr, N);
System.out.println(res);
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python 3 code to implement the approach # Function to calculate the maximum value def MaximiseStockPurchase(nums, n): maxi = 0 for i in range(n): maxi = max(maxi, nums[i]) freq = [0]*(maxi + 1) dp = [0] * (maxi + 1) for i in nums: freq[i] += 1 dp[1] = freq[1] # Loop to calculate dp[] array # till max element of array for i in range(2, maxi + 1): dp[i] = max(dp[i - 2] + i * freq[i], dp[i - 1]) return dp[maxi] # Driver code if __name__ == "__main__": arr = [2, 2, 3, 4, 3, 3] N = len(arr) res = MaximiseStockPurchase(arr, N) print(res) # This code is contributed by ukasp.
C#
// C# code to implement the approach
using System;
class GFG {
// Function to calculate the maximum value
static int MaximiseStockPurchase(int[] nums, int n)
{
int maxi = 0;
for (int i = 0; i < n; i++)
maxi = Math.Max(maxi, nums[i]);
int[] freq = new int[maxi + 1];
int[] dp = new int[maxi + 1];
for (int i = 0; i < n; i++)
freq[nums[i]]++;
dp[1] = freq[1];
// Loop to calculate dp[] array
// till max element of array
for (int i = 2; i <= maxi; i++)
dp[i] = Math.Max(dp[i - 2] + i * freq[i],
dp[i - 1]);
return dp[maxi];
}
// Driver code
public static void Main()
{
int[] arr = { 2, 2, 3, 4, 3, 3 };
int N = arr.Length;
int res = MaximiseStockPurchase(arr, N);
Console.WriteLine(res);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code to implement the approach
// Function to calculate the maximum value
const MaximiseStockPurchase = (nums, n) => {
let maxi = 0;
for (let i = 0; i < n; i++)
maxi = Math.max(maxi, nums[i]);
let freq = new Array(maxi + 1).fill(0);
let dp = new Array(maxi + 1).fill(0);
for (let i in nums)
freq[nums[i]]++;
dp[1] = freq[1];
// Loop to calculate dp[] array
// till max element of array
for (let i = 2; i <= maxi; i++)
dp[i] = Math.max(dp[i - 2] + i * freq[i],
dp[i - 1]);
return dp[maxi];
}
// Driver code
let arr = [2, 2, 3, 4, 3, 3];
let N = arr.length;
let res = MaximiseStockPurchase(arr, N);
document.write(res);
// This code is contributed by rakeshsahni
</script>
9
Complejidad temporal: O(M) donde M es el elemento máximo del arreglo.
Espacio Auxiliar : O(M)
Enfoque alternativo: en el enfoque anterior, el espacio de la array dp[] se puede optimizar de la siguiente manera:
Como se ve en la observación, solo necesitamos el valor de dp[i-1] y dp[i-2] para calcular el valor de dp[i]. Entonces, en lugar de usar la array dp[], use dos variables para almacenar el valor de los dos pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the maximum sum
int MaximiseStockPurchase(vector<int>& nums,
int n)
{
int maxNum = INT_MIN;
for (auto i : nums)
maxNum = max(maxNum, i);
vector<int> freq(maxNum + 1, 0);
for (auto i : nums)
freq[i]++;
int curPoints = freq[1], prevPoints = 0;
// Loop to calculate the sum
for (int i = 2; i <= maxNum; i++) {
int tmp = curPoints;
curPoints = max(prevPoints + i * freq[i],
curPoints);
prevPoints = tmp;
}
return curPoints;
}
// Driver code
int main()
{
vector<int> arr{ 2, 2, 3, 4, 3, 3 };
int N = arr.size();
int res = MaximiseStockPurchase(arr, N);
cout << res;
return 0;
}
Java
// Java implementation of above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to calculate the maximum sum
static int MaximiseStockPurchase(int[] nums, int n)
{
int maxNum = Integer.MIN_VALUE;
for(int i : nums) maxNum = Math.max(maxNum, i);
int[] freq = new int[maxNum + 1];
for (int x = 0; x < maxNum; x++) {
freq[x] = 0;
}
for(int i : nums) freq[i]++;
int curPoints = freq[1], prevPoints = 0;
// Loop to calculate the sum
for (int i = 2; i <= maxNum; i++) {
int tmp = curPoints;
curPoints = Math.max(prevPoints + i * freq[i],
curPoints);
prevPoints = tmp;
}
return curPoints;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 2, 3, 4, 3, 3 };
int N = arr.length;
int res = MaximiseStockPurchase(arr, N);
System.out.print(res);
}
}
// This code is contributed by code_hunt.
Python3
# Python code to implement the approach # Function to calculate the maximum sum import sys def MaximiseStockPurchase(nums,n): maxNum = -sys.maxsize -1 for i in nums: maxNum = max(maxNum, i) freq = [0 for i in range(maxNum+1)] for i in nums: freq[i] += 1 curPoints,prevPoints = freq[1],0 # Loop to calculate the sum for i in range(2,maxNum+1): tmp = curPoints curPoints = max(prevPoints + i * freq[i],curPoints) prevPoints = tmp return curPoints # Driver code arr = [ 2, 2, 3, 4, 3, 3 ] N = len(arr) res = MaximiseStockPurchase(arr, N) print(res) # This code is contributed by shinjanpatra
C#
// C# code to implement the approach
using System;
class GFG {
// Function to calculate the maximum sum
static int MaximiseStockPurchase(int[] nums, int n)
{
int maxNum = Int32.MinValue;
foreach(int i in nums) maxNum = Math.Max(maxNum, i);
int[] freq = new int[maxNum + 1];
for (int x = 0; x < maxNum; x++) {
freq[x] = 0;
}
foreach(int i in nums) freq[i]++;
int curPoints = freq[1], prevPoints = 0;
// Loop to calculate the sum
for (int i = 2; i <= maxNum; i++) {
int tmp = curPoints;
curPoints = Math.Max(prevPoints + i * freq[i],
curPoints);
prevPoints = tmp;
}
return curPoints;
}
// Driver code
public static void Main()
{
int[] arr = { 2, 2, 3, 4, 3, 3 };
int N = arr.Length;
int res = MaximiseStockPurchase(arr, N);
Console.Write(res);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code to implement the approach
// Function to calculate the maximum sum
function MaximiseStockPurchase(nums,n)
{
let maxNum = Number.MIN_VALUE;
for (let i of nums)
maxNum = Math.max(maxNum, i);
let freq = new Array(maxNum + 1).fill(0);
for (let i of nums)
freq[i]++;
let curPoints = freq[1], prevPoints = 0;
// Loop to calculate the sum
for (let i = 2; i <= maxNum; i++) {
let tmp = curPoints;
curPoints = Math.max(prevPoints + i * freq[i],
curPoints);
prevPoints = tmp;
}
return curPoints;
}
// Driver code
let arr = [ 2, 2, 3, 4, 3, 3 ];
let N = arr.length;
let res = MaximiseStockPurchase(arr, N);
document.write(res);
// This code is contributed by shinjanpatra
</script>
9
Complejidad temporal : O(N + M) donde M es el elemento máximo del arreglo
Espacio auxiliar: O(M).
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA