Dada una array A que contiene N enteros. Encuentre la suma máxima posible tal que se seleccionen los elementos exactos del piso (N/2) y que no haya dos elementos seleccionados adyacentes entre sí. (si N = 5, entonces se deben seleccionar exactamente 2 elementos como piso (5/2) = 2)
Para una versión más simple de este problema, consulte este .
Ejemplos:
Entrada: A = [1, 2, 3, 4, 5, 6]
Salida: 12
Explicación:
Seleccione 2, 4 y 6 haciendo la suma 12.Entrada: A = [-1000, -100, -10, 0, 10]
Salida: 0
Explicación:
Seleccione -10 y 10, haciendo la suma 0.
Acercarse:
- Utilizaremos el concepto de programación dinámica. Así es como se definen los estados de dp:
dp[i][j] = suma máxima hasta el índice i tal que se seleccionan j elementos
- Dado que no se pueden seleccionar dos elementos adyacentes:
dp[i][j] = max(a[i] + dp[i-2][j-1], dp[i-1][j])
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find maximum sum possible
// such that exactly floor(N/2) elements
// are selected and no two selected
// elements are adjacent to each other
#include <bits/stdc++.h>
using namespace std;
// Function return the maximum sum
// possible under given condition
int MaximumSum(int a[], int n)
{
int dp[n + 1][n + 1];
// Intitialising the dp table
for (int i = 0; i < n + 1; i++)
{
for (int j = 0; j < n + 1; j++)
dp[i][j] = INT_MIN;
}
// Base case
for (int i = 0; i < n + 1; i++)
dp[i][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
int val = INT_MIN;
// Condition to select the current
// element
if ((i - 2 >= 0
&& dp[i - 2][j - 1] != INT_MIN)
|| i - 2 < 0)
{
val = a[i - 1] +
(i - 2 >= 0 ?
dp[i - 2][j - 1] : 0);
}
// Condition to not select the
// current element if possible
if (i - 1 >= j)
{
val = max(val, dp[i - 1][j]);
}
dp[i][j] = val;
}
}
return dp[n][n / 2];
}
//Driver code
int main()
{
int A[] = {1, 2, 3, 4, 5, 6};
int N = sizeof(A) / sizeof(A[0]);
cout << MaximumSum(A, N);
return 0;
}
Java
// Java program to find maximum sum possible
// such that exactly Math.floor(N/2) elements
// are selected and no two selected
// elements are adjacent to each other
class GFG{
// Function return the maximum sum
// possible under given condition
static int MaximumSum(int a[], int n)
{
int [][]dp = new int[n + 1][n + 1];
// Intitialising the dp table
for(int i = 0; i < n + 1; i++)
{
for(int j = 0; j < n + 1; j++)
dp[i][j] = Integer.MIN_VALUE;
}
// Base case
for(int i = 0; i < n + 1; i++)
dp[i][0] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
int val = Integer.MIN_VALUE;
// Condition to select the current
// element
if ((i - 2 >= 0 &&
dp[i - 2][j - 1] != Integer.MIN_VALUE) ||
i - 2 < 0)
{
val = a[i - 1] + (i - 2 >= 0 ?
dp[i - 2][j - 1] : 0);
}
// Condition to not select the
// current element if possible
if (i - 1 >= j)
{
val = Math.max(val, dp[i - 1][j]);
}
dp[i][j] = val;
}
}
return dp[n][n / 2];
}
// Driver code
public static void main(String[] args)
{
int A[] = { 1, 2, 3, 4, 5, 6 };
int N = A.length;
System.out.print(MaximumSum(A, N));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find maximum sum possible # such that exactly floor(N/2) elements # are selected and no two selected # elements are adjacent to each other import sys # Function return the maximum sum # possible under given condition def MaximumSum(a,n): dp = [[0 for i in range(n+1)] for j in range(n+1)] # Intitialising the dp table for i in range(n + 1): for j in range(n + 1): dp[i][j] = -sys.maxsize-1 # Base case for i in range(n+1): dp[i][0] = 0 for i in range(1,n+1,1): for j in range(1,i+1,1): val = -sys.maxsize-1 # Condition to select the current # element if ((i - 2 >= 0 and dp[i - 2][j - 1] != -sys.maxsize-1) or i - 2 < 0): if (i - 2 >= 0): val = a[i - 1] + dp[i - 2][j - 1] else: val = a[i - 1] # Condition to not select the # current element if possible if (i - 1 >= j): val = max(val, dp[i - 1][j]) dp[i][j] = val return dp[n][n // 2] #Driver code if __name__ == '__main__': A = [1, 2, 3, 4, 5, 6] N = len(A) print(MaximumSum(A,N)) # This code is contributed by Bhupendra_Singh
C#
// C# program to find maximum sum possible
// such that exactly Math.floor(N/2) elements
// are selected and no two selected
// elements are adjacent to each other
using System;
class GFG{
// Function return the maximum sum
// possible under given condition
static int MaximumSum(int []a, int n)
{
int [,]dp = new int[n + 1, n + 1];
// Intitialising the dp table
for(int i = 0; i < n + 1; i++)
{
for(int j = 0; j < n + 1; j++)
dp[i, j] = Int32.MinValue;
}
// Base case
for(int i = 0; i < n + 1; i++)
dp[i, 0] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
int val = Int32.MinValue;
// Condition to select the current
// element
if ((i - 2 >= 0 &&
dp[i - 2, j - 1] != Int32.MinValue) ||
i - 2 < 0)
{
val = a[i - 1] + (i - 2 >= 0 ?
dp[i - 2, j - 1] : 0);
}
// Condition to not select the
// current element if possible
if (i - 1 >= j)
{
val = Math.Max(val, dp[i - 1, j]);
}
dp[i, j] = val;
}
}
return dp[n, n / 2];
}
// Driver code
public static void Main()
{
int []A = { 1, 2, 3, 4, 5, 6 };
int N = A.Length;
Console.Write(MaximumSum(A, N));
}
}
// This code is contributed by Nidhi_biet
Javascript
<script>
// JavaScript program to find maximum sum possible
// such that exactly Math.floor(N/2) elements
// are selected and no two selected
// elements are adjacent to each other
// Function return the maximum sum
// possible under given condition
function MaximumSum(a,n)
{
let dp = [];
for(let i=0;i<n+1;i++) dp.push(Array(n+1));
// Intitialising the dp table
for(let i = 0; i < n + 1; i++)
{
for(let j = 0; j < n + 1; j++)
dp[i][j] = -10000;
}
// Base case
for(let i = 0; i < n + 1; i++)
dp[i][0] = 0;
for(let i = 1; i <= n; i++)
{
for(let j = 1; j <= i; j++)
{
let val = -10000;
// Condition to select the current
// element
if ((i - 2 >= 0 &&
dp[i - 2, j - 1] != -10000) ||
i - 2 < 0)
{
val = a[i - 1] + (i - 2 >= 0 ?
dp[i - 2][j - 1] : 0);
}
// Condition to not select the
// current element if possible
if (i - 1 >= j)
{
val = Math.max(val, dp[i - 1][j]);
}
dp[i][j] = val;
}
}
return dp[n][n / 2]
}
// Driver code
let A = [1, 2, 3, 4, 5, 6];
let N = A.length;
document.write(MaximumSum(A, N));
// This code is contributed by Nidhi_biet
</script>
Producción:
12
Tiempo Complejidad : O(N 2 )
Enfoque eficiente
- Usaremos programación dinámica pero con estados ligeramente modificados. Almacenar tanto el índice como el número de elementos tomados hasta ahora es inútil ya que siempre necesitamos tomar los elementos del piso (i/2) exactos, por lo que en la i-ésima posición para el almacenamiento de dp asumiremos los elementos del piso (i/2) en el subconjunto hasta ahora.
- Los siguientes son los estados de la tabla dp:
dp[i][1] = suma máxima hasta el i-ésimo índice, seleccionando el elemento a[i], con elementos floor(i/2), ninguno adyacente entre sí.
dp[i][0] = suma máxima hasta el i-ésimo índice, sin seleccionar el elemento a[i], con elementos de piso (i/2), ninguno adyacente entre sí.
- Tenemos dos casos:
- Cuando i es impar : si tenemos que elegir a[i], entonces no podemos elegir a[i-1], por lo que las únicas opciones que quedan son (i – 2)th y (i – 3) rd state (porque piso((i – 2)/2) = piso((i – 3)/2) = piso(i/2) – 1, y dado que elegimos a[i], el total de elementos seleccionados será piso(i/2 ) ). Si no elegimos a[i], entonces se formará una suma tomando a[i-1] y usando los estados i – 1, i – 2 e i – 3 o a[i – 2] usando el estado i – 3 ya que estos solo darán el total de piso (i/2).
dp[i][1] = arr[i] + max({dp[i – 3][1], dp[i – 3][0], dp[i – 2][1], dp[i – 2][0]})
dp[i][0] = max({arr[i – 1] + dp[i – 2][0], arr[i – 1] + dp[i – 3][1 ], dirección[i – 1] + dp[i – 3][0],
dirección[i – 2] + dp[i – 3][0]})
- Cuando i es par : si elegimos a[i], luego usamos los estados i – 1 e i – 2, de lo contrario, elegimos a[i – 1] y usamos el estado i – 2.
dp[i][1] = arr[i] + max({dp[i – 2][1], dp[i – 2][0], dp[i – 1][0]})
dp[i ][0] = arr[i – 1] + dp[i – 2][0]
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find maximum sum possible
// such that exactly floor(N/2) elements
// are selected and no two selected
// elements are adjacent to each other
#include <bits/stdc++.h>
using namespace std;
// Function return the maximum sum
// possible under given condition
int MaximumSum(int a[], int n)
{
int dp[n + 1][2];
// Intitialising the dp table
memset(dp, 0, sizeof(dp));
// Base case
dp[2][1] = a[1];
dp[2][0] = a[0];
for (int i = 3; i < n + 1; i++) {
// When i is odd
if (i & 1) {
int temp = max({ dp[i - 3][1],
dp[i - 3][0],
dp[i - 2][1],
dp[i - 2][0] });
dp[i][1] = a[i - 1] + temp;
dp[i][0] = max({ a[i - 2] + dp[i - 2][0],
a[i - 2] + dp[i - 3][1],
a[i - 2] + dp[i - 3][0],
a[i - 3] + dp[i - 3][0] });
}
// When i is even
else {
dp[i][1] = a[i - 1] + max({ dp[i - 2][1],
dp[i - 2][0],
dp[i - 1][0] });
dp[i][0] = a[i - 2] + dp[i - 2][0];
}
}
// Maximum of if we pick last element or not
return max(dp[n][1], dp[n][0]);
}
// Driver code
int main()
{
int A[] = {1, 2, 3, 4, 5, 6};
int N = sizeof(A) / sizeof(A[0]);
cout << MaximumSum(A, N);
return 0;
}
Java
// Java program to find maximum sum possible
// such that exactly Math.floor(N/2) elements
// are selected and no two selected
// elements are adjacent to each other
import java.util.*;
class GFG{
// Function return the maximum sum
// possible under given condition
static int MaximumSum(int a[], int n)
{
int [][]dp = new int[n + 1][2];
// Base case
dp[2][1] = a[1];
dp[2][0] = a[0];
for(int i = 3; i < n + 1; i++)
{
// When i is odd
if (i % 2 == 1)
{
int temp = Math.max((Math.max(dp[i - 3][1],
dp[i - 3][0])),
Math.max(dp[i - 2][1],
dp[i - 2][0]));
dp[i][1] = a[i - 1] + temp;
dp[i][0] = Math.max((Math.max(a[i - 2] +
dp[i - 2][0],
a[i - 2] +
dp[i - 3][1])),
Math.max(a[i - 2] +
dp[i - 3][0],
a[i - 3] +
dp[i - 3][0]));
}
// When i is even
else
{
dp[i][1] = a[i - 1] + (Math.max((
Math.max(dp[i - 2][1],
dp[i - 2][0])),
dp[i - 1][0]));
dp[i][0] = a[i - 2] + dp[i - 2][0];
}
}
// Maximum of if we pick last element or not
return Math.max(dp[n][1], dp[n][0]);
}
static int max(int []arr)
{
return 1;
}
// Driver code
public static void main(String[] args)
{
int A[] = {1, 2, 3, 4, 5, 6};
int N = A.length;
System.out.print(MaximumSum(A, N));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find maximum sum possible # such that exactly floor(N/2) elements # are selected and no two selected # elements are adjacent to each other # Function return the maximum sum # possible under given condition def MaximumSum(a, n): dp = [[0 for x in range (2)] for y in range(n + 1)] # Base case dp[2][1] = a[1] dp[2][0] = a[0] for i in range (3, n + 1): # When i is odd if (i & 1): temp = max([dp[i - 3][1], dp[i - 3][0], dp[i - 2][1], dp[i - 2][0]]) dp[i][1] = a[i - 1] + temp dp[i][0] = max([a[i - 2] + dp[i - 2][0], a[i - 2] + dp[i - 3][1], a[i - 2] + dp[i - 3][0], a[i - 3] + dp[i - 3][0]]) # When i is even else: dp[i][1] = (a[i - 1] + max([dp[i - 2][1], dp[i - 2][0], dp[i - 1][0]])) dp[i][0] = a[i - 2] + dp[i - 2][0] # Maximum of if we pick last # element or not return max(dp[n][1], dp[n][0]) # Driver code if __name__ == "__main__": A = [1, 2, 3, 4, 5, 6] N = len(A) print(MaximumSum(A, N)) # This code is contributed by Chitranayal
C#
// C# program to find maximum sum possible
// such that exactly Math.Floor(N/2) elements
// are selected and no two selected
// elements are adjacent to each other
using System;
class GFG{
// Function return the maximum sum
// possible under given condition
static int MaximumSum(int []a, int n)
{
int [,]dp = new int[n + 1, 2];
// Base case
dp[2, 1] = a[1];
dp[2, 0] = a[0];
for(int i = 3; i < n + 1; i++)
{
// When i is odd
if (i % 2 == 1)
{
int temp = Math.Max((Math.Max(dp[i - 3, 1],
dp[i - 3, 0])),
Math.Max(dp[i - 2, 1],
dp[i - 2, 0]));
dp[i, 1] = a[i - 1] + temp;
dp[i, 0] = Math.Max((Math.Max(a[i - 2] +
dp[i - 2, 0],
a[i - 2] +
dp[i - 3, 1])),
Math.Max(a[i - 2] +
dp[i - 3, 0],
a[i - 3] +
dp[i - 3, 0]));
}
// When i is even
else
{
dp[i, 1] = a[i - 1] + (Math.Max((
Math.Max(dp[i - 2, 1],
dp[i - 2, 0])),
dp[i - 1, 0]));
dp[i, 0] = a[i - 2] + dp[i - 2, 0];
}
}
// Maximum of if we pick last element or not
return Math.Max(dp[n, 1], dp[n, 0]);
}
static int max(int []arr)
{
return 1;
}
// Driver code
public static void Main(String[] args)
{
int []A = { 1, 2, 3, 4, 5, 6 };
int N = A.Length;
Console.Write(MaximumSum(A, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find maximum sum possible
// such that exactly floor(N/2) elements
// are selected and no two selected
// elements are adjacent to each other
// Function return the maximum sum
// possible under given condition
function MaximumSum(a, n)
{
var dp = Array.from(Array(n+1), ()=>Array(2).fill(0));
// Base case
dp[2][1] = a[1];
dp[2][0] = a[0];
for (var i = 3; i < n + 1; i++) {
// When i is odd
if (i & 1) {
var temp = ([dp[i - 3][1],
dp[i - 3][0],
dp[i - 2][1],
dp[i - 2][0] ].reduce((a,b)=>
Math.max(a,b)));
dp[i][1] = a[i - 1] + temp;
dp[i][0] = ([ a[i - 2] + dp[i - 2][0],
a[i - 2] + dp[i - 3][1],
a[i - 2] + dp[i - 3][0],
a[i - 3] + dp[i - 3][0] ].reduce((a,b)=>
Math.max(a,b)));
}
// When i is even
else {
dp[i][1] = a[i - 1] + ([ dp[i - 2][1],
dp[i - 2][0],
dp[i - 1][0] ].reduce((a,b)=>
Math.max(a,b)));
dp[i][0] = a[i - 2] + dp[i - 2][0];
}
}
// Maximum of if we pick last element or not
return Math.max(dp[n][1], dp[n][0]);
}
// Driver code
var A = [1, 2, 3, 4, 5, 6];
var N = A.length;
document.write( MaximumSum(A, N));
</script>
Producción:
12
Complejidad de tiempo: O(N)