Dada una array A de tamaño N , la tarea es encontrar la puntuación máxima posible de esta array. La puntuación de una array se calcula realizando las siguientes operaciones en la array N veces:
- Si la operación tiene un número impar, la puntuación se incrementa por la suma de todos los elementos de la array actual.
- Si la operación es par, la puntuación se reduce por la suma de todos los elementos de la array actual.
- Después de cada operación, elimine el primer o el último elemento de la array restante.
Ejemplos:
Entrada: A = {1, 2, 3, 4, 2, 6}
Salida: 13
Explicación:
Las operaciones óptimas son:
1. La operación 1 es impar.
-> Entonces agregue la suma de la array a la puntuación: Puntuación = 0 + 18 = 18
-> elimine 6 de la última
-> nueva array A = [1, 2, 3, 4, 2]
2. La operación 2 es par .
-> Así que reste la suma de la array de la puntuación: Puntuación = 18 – 12 = 6
-> elimine 2 de la última
-> nueva array A = [1, 2, 3, 4]
3. La operación 1 es impar.
-> Entonces agregue la suma de la array a la puntuación: Puntuación = 6 + 10 = 16
-> elimine 4 de la última
-> nueva array A = [1, 2, 3]
4. La operación 4 es par.
-> Así que reste la suma de la array de la puntuación: Puntuación = 16 – 6 = 10
-> elimine 1 del inicio,
-> nueva array A = [2, 3]
5. La operación 5 es impar.
-> Así que agregue la suma de la array a la puntuación: Puntuación = 10 + 5 = 15
-> elimine 3 de la última,
-> nueva array A = [2]
6. La operación 6 es par.
-> Así que reste la suma de la array de la puntuación: Puntuación = 15 – 2 = 13
-> elimine 2 del primero,
-> nueva array A = []
La array está vacía, por lo que no es posible realizar más operaciones.
Entrada: A = [5, 2, 2, 8, 1, 16, 7, 9, 12, 4]
Salida: 50
Enfoque ingenuo
- En cada operación, tenemos que eliminar el elemento más a la izquierda o el más a la derecha. Una forma sencilla sería considerar todas las formas posibles de eliminar elementos y para cada rama calcular la puntuación y encontrar la puntuación máxima de todas. Esto se puede hacer simplemente usando recursividad .
- La información que debemos mantener en cada paso sería
- La array restante [l, r] , donde l representa el índice más a la izquierda y r el más a la derecha,
- El número de operación y
- La puntuación actual.
- Para calcular la suma de cualquier array de [l, r] en cada paso recursivo de manera óptima, mantendremos una array de suma de prefijos .
Usando la array de suma de prefijos, la nueva suma de [l, r] se puede calcular en O (1) como:
Suma(l, r) = suma_prefijo[r] – suma_prefijo[l-1]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the maximum
// score after given operations
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// maximum score recursively
int maxScore(
int l, int r,
int prefix_sum[],
int num)
{
// Base case
if (l > r)
return 0;
// Sum of array in range (l, r)
int current_sum
= prefix_sum[r]
- (l - 1 >= 0
? prefix_sum[l - 1]
: 0);
// If the operation is even-numbered
// the score is decremented
if (num % 2 == 0)
current_sum *= -1;
// Exploring all paths, by removing
// leftmost and rightmost element
// and selecting the maximum value
return current_sum
+ max(
maxScore(
l + 1, r,
prefix_sum,
num + 1),
maxScore(
l, r - 1,
prefix_sum,
num + 1));
}
// Function to find the max score
int findMaxScore(int a[], int n)
{
// Prefix sum array
int prefix_sum[n] = { 0 };
prefix_sum[0] = a[0];
// Calculating prefix_sum
for (int i = 1; i < n; i++) {
prefix_sum[i]
= prefix_sum[i - 1] + a[i];
}
return maxScore(0, n - 1,
prefix_sum, 1);
}
// Driver code
int main()
{
int n = 6;
int A[n] = { 1, 2, 3, 4, 2, 6 };
cout << findMaxScore(A, n);
return 0;
}
Java
// Java program to find the maximum
// score after given operations
import java.util.*;
class GFG{
// Function to calculate
// maximum score recursively
static int maxScore(
int l, int r,
int prefix_sum[],
int num)
{
// Base case
if (l > r)
return 0;
// Sum of array in range (l, r)
int current_sum
= prefix_sum[r]
- (l - 1 >= 0
? prefix_sum[l - 1]
: 0);
// If the operation is even-numbered
// the score is decremented
if (num % 2 == 0)
current_sum *= -1;
// Exploring all paths, by removing
// leftmost and rightmost element
// and selecting the maximum value
return current_sum
+ Math.max(maxScore(l + 1, r,
prefix_sum,
num + 1),
maxScore(l, r - 1,
prefix_sum,
num + 1));
}
// Function to find the max score
static int findMaxScore(int a[], int n)
{
// Prefix sum array
int prefix_sum[] = new int[n];
prefix_sum[0] = a[0];
// Calculating prefix_sum
for (int i = 1; i < n; i++) {
prefix_sum[i]
= prefix_sum[i - 1] + a[i];
}
return maxScore(0, n - 1,
prefix_sum, 1);
}
// Driver code
public static void main(String[] args)
{
int n = 6;
int A[] = { 1, 2, 3, 4, 2, 6 };
System.out.print(findMaxScore(A, n));
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program to find the maximum # score after given operations # Function to calculate maximum # score recursively def maxScore(l, r, prefix_sum, num): # Base case if (l > r): return 0; # Sum of array in range (l, r) if((l - 1) >= 0): current_sum = (prefix_sum[r] - prefix_sum[l - 1]) else: current_sum = prefix_sum[r] - 0 # If the operation is even-numbered # the score is decremented if (num % 2 == 0): current_sum *= -1; # Exploring all paths, by removing # leftmost and rightmost element # and selecting the maximum value return current_sum + max(maxScore(l + 1, r, prefix_sum, num + 1), maxScore(l, r - 1, prefix_sum, num + 1)); # Function to find the max score def findMaxScore(a, n): # Prefix sum array prefix_sum = [0] * n prefix_sum[0] = a[0] # Calculating prefix_sum for i in range(1, n): prefix_sum[i] = prefix_sum[i - 1] + a[i]; return maxScore(0, n - 1, prefix_sum, 1); # Driver code n = 6; A = [ 1, 2, 3, 4, 2, 6 ] ans = findMaxScore(A, n) print(ans) # This code is contributed by SoumikMondal
C#
// C# program to find the maximum
// score after given operations
using System;
class GFG{
// Function to calculate
// maximum score recursively
static int maxScore(
int l, int r,
int []prefix_sum,
int num)
{
// Base case
if (l > r)
return 0;
// Sum of array in range (l, r)
int current_sum
= prefix_sum[r]
- (l - 1 >= 0
? prefix_sum[l - 1]
: 0);
// If the operation is even-numbered
// the score is decremented
if (num % 2 == 0)
current_sum *= -1;
// Exploring all paths, by removing
// leftmost and rightmost element
// and selecting the maximum value
return current_sum
+ Math.Max(maxScore(l + 1, r,
prefix_sum,
num + 1),
maxScore(l, r - 1,
prefix_sum,
num + 1));
}
// Function to find the max score
static int findMaxScore(int []a, int n)
{
// Prefix sum array
int []prefix_sum = new int[n];
prefix_sum[0] = a[0];
// Calculating prefix_sum
for (int i = 1; i < n; i++) {
prefix_sum[i]
= prefix_sum[i - 1] + a[i];
}
return maxScore(0, n - 1,
prefix_sum, 1);
}
// Driver code
public static void Main(String[] args)
{
int n = 6;
int []A = { 1, 2, 3, 4, 2, 6 };
Console.Write(findMaxScore(A, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find the maximum
// score after given operations
// Function to calculate
// maximum score recursively
function maxScore(l, r, prefix_sum, num)
{
// Base case
if (l > r)
return 0;
// Sum of array in range (l, r)
let current_sum
= prefix_sum[r]
- (l - 1 >= 0
? prefix_sum[l - 1]
: 0);
// If the operation is even-numbered
// the score is decremented
if (num % 2 == 0)
current_sum *= -1;
// Exploring all paths, by removing
// leftmost and rightmost element
// and selecting the maximum value
return current_sum
+ Math.max(
maxScore(
l + 1, r,
prefix_sum,
num + 1),
maxScore(
l, r - 1,
prefix_sum,
num + 1));
}
// Function to find the max score
function findMaxScore(a, n)
{
// Prefix sum array
let prefix_sum = new Uint8Array(n);
prefix_sum[0] = a[0];
// Calculating prefix_sum
for (let i = 1; i < n; i++) {
prefix_sum[i]
= prefix_sum[i - 1] + a[i];
}
return maxScore(0, n - 1,
prefix_sum, 1);
}
// Driver code
let n = 6;
let A = [ 1, 2, 3, 4, 2, 6 ];
document.write(findMaxScore(A, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
13
Complejidad temporal: O(2 N )
Enfoque eficiente
- En el enfoque anterior se puede observar que estamos calculando los mismos subproblemas muchas veces, es decir, sigue la propiedad de Superposición de subproblemas . Entonces podemos usar la programación dinámica para resolver el problema.
- En la solución recursiva mencionada anteriormente, solo necesitamos agregar memorización usando una tabla dp . Los estados serán:
Estados de la tabla DP = dp[l][r][num]
donde l y r representan los puntos finales de la array actual y num representa el número de operación.
A continuación se muestra la implementación del enfoque Memoization del código recursivo:
C++
// C++ program to find the maximum
// Score after given operations
#include <bits/stdc++.h>
using namespace std;
// Memoizing by the use of a table
int dp[100][100][100];
// Function to calculate maximum score
int MaximumScoreDP(int l, int r,
int prefix_sum[],
int num)
{
// Bse case
if (l > r)
return 0;
// If the same state has
// already been computed
if (dp[l][r][num] != -1)
return dp[l][r][num];
// Sum of array in range (l, r)
int current_sum
= prefix_sum[r]
- (l - 1 >= 0
? prefix_sum[l - 1]
: 0);
// If the operation is even-numbered
// the score is decremented
if (num % 2 == 0)
current_sum *= -1;
// Exploring all paths, and storing
// maximum value in DP table to avoid
// further repetitive recursive calls
dp[l][r][num] = current_sum
+ max(
MaximumScoreDP(
l + 1, r,
prefix_sum,
num + 1),
MaximumScoreDP(
l, r - 1,
prefix_sum,
num + 1));
return dp[l][r][num];
}
// Function to find the max score
int findMaxScore(int a[], int n)
{
// Prefix sum array
int prefix_sum[n] = { 0 };
prefix_sum[0] = a[0];
// Calculating prefix_sum
for (int i = 1; i < n; i++) {
prefix_sum[i]
= prefix_sum[i - 1] + a[i];
}
// Initialising the DP table,
// -1 represents the subproblem
// hasn't been solved yet
memset(dp, -1, sizeof(dp));
return MaximumScoreDP(
0, n - 1,
prefix_sum, 1);
}
// Driver code
int main()
{
int n = 6;
int A[n] = { 1, 2, 3, 4, 2, 6 };
cout << findMaxScore(A, n);
return 0;
}
Java
// Java program to find the maximum
// Score after given operations
class GFG{
// Memoizing by the use of a table
static int [][][]dp = new int[100][100][100];
// Function to calculate maximum score
static int MaximumScoreDP(int l, int r,
int prefix_sum[],
int num)
{
// Bse case
if (l > r)
return 0;
// If the same state has
// already been computed
if (dp[l][r][num] != -1)
return dp[l][r][num];
// Sum of array in range (l, r)
int current_sum
= prefix_sum[r]
- (l - 1 >= 0
? prefix_sum[l - 1]
: 0);
// If the operation is even-numbered
// the score is decremented
if (num % 2 == 0)
current_sum *= -1;
// Exploring all paths, and storing
// maximum value in DP table to avoid
// further repetitive recursive calls
dp[l][r][num] = current_sum
+ Math.max(
MaximumScoreDP(
l + 1, r,
prefix_sum,
num + 1),
MaximumScoreDP(
l, r - 1,
prefix_sum,
num + 1));
return dp[l][r][num];
}
// Function to find the max score
static int findMaxScore(int a[], int n)
{
// Prefix sum array
int []prefix_sum = new int[n];
prefix_sum[0] = a[0];
// Calculating prefix_sum
for (int i = 1; i < n; i++) {
prefix_sum[i]
= prefix_sum[i - 1] + a[i];
}
// Initialising the DP table,
// -1 represents the subproblem
// hasn't been solved yet
for(int i = 0;i<100;i++){
for(int j = 0;j<100;j++){
for(int l=0;l<100;l++)
dp[i][j][l]=-1;
}
}
return MaximumScoreDP(
0, n - 1,
prefix_sum, 1);
}
// Driver code
public static void main(String[] args)
{
int n = 6;
int A[] = { 1, 2, 3, 4, 2, 6 };
System.out.print(findMaxScore(A, n));
}
}
// This code contributed by sapnasingh4991
Python3
# python3 program to find the maximum # Score after given operations # Memoizing by the use of a table dp = [[[-1 for x in range(100)]for y in range(100)]for z in range(100)] # Function to calculate maximum score def MaximumScoreDP(l, r, prefix_sum, num): # Bse case if (l > r): return 0 # If the same state has # already been computed if (dp[l][r][num] != -1): return dp[l][r][num] # Sum of array in range (l, r) current_sum = prefix_sum[r] if (l - 1 >= 0): current_sum -= prefix_sum[l - 1] # If the operation is even-numbered # the score is decremented if (num % 2 == 0): current_sum *= -1 # Exploring all paths, and storing # maximum value in DP table to avoid # further repetitive recursive calls dp[l][r][num] = (current_sum + max( MaximumScoreDP( l + 1, r, prefix_sum, num + 1), MaximumScoreDP( l, r - 1, prefix_sum, num + 1))) return dp[l][r][num] # Function to find the max score def findMaxScore(a, n): # Prefix sum array prefix_sum = [0]*n prefix_sum[0] = a[0] # Calculating prefix_sum for i in range(1, n): prefix_sum[i] = prefix_sum[i - 1] + a[i] # Initialising the DP table, # -1 represents the subproblem # hasn't been solved yet global dp return MaximumScoreDP( 0, n - 1, prefix_sum, 1) # Driver code if __name__ == "__main__": n = 6 A = [1, 2, 3, 4, 2, 6] print(findMaxScore(A, n))
C#
// C# program to find the maximum
// Score after given operations
using System;
public class GFG{
// Memoizing by the use of a table
static int [,,]dp = new int[100,100,100];
// Function to calculate maximum score
static int MaximumScoreDP(int l, int r,
int []prefix_sum,
int num)
{
// Bse case
if (l > r)
return 0;
// If the same state has
// already been computed
if (dp[l,r,num] != -1)
return dp[l,r,num];
// Sum of array in range (l, r)
int current_sum
= prefix_sum[r]
- (l - 1 >= 0
? prefix_sum[l - 1]
: 0);
// If the operation is even-numbered
// the score is decremented
if (num % 2 == 0)
current_sum *= -1;
// Exploring all paths, and storing
// maximum value in DP table to avoid
// further repetitive recursive calls
dp[l,r,num] = current_sum
+ Math.Max(
MaximumScoreDP(
l + 1, r,
prefix_sum,
num + 1),
MaximumScoreDP(
l, r - 1,
prefix_sum,
num + 1));
return dp[l,r,num];
}
// Function to find the max score
static int findMaxScore(int []a, int n)
{
// Prefix sum array
int []prefix_sum = new int[n];
prefix_sum[0] = a[0];
// Calculating prefix_sum
for (int i = 1; i < n; i++) {
prefix_sum[i]
= prefix_sum[i - 1] + a[i];
}
// Initialising the DP table,
// -1 represents the subproblem
// hasn't been solved yet
for(int i = 0;i<100;i++){
for(int j = 0;j<100;j++){
for(int l=0;l<100;l++)
dp[i,j,l]=-1;
}
}
return MaximumScoreDP(
0, n - 1,
prefix_sum, 1);
}
// Driver code
public static void Main(String[] args)
{
int n = 6;
int []A = { 1, 2, 3, 4, 2, 6 };
Console.Write(findMaxScore(A, n));
}
}
// This code contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to find the maximum
// Score after given operations
// Memoizing by the use of a table
let dp = new Array(100);
// Initialising the DP table,
// -1 represents the subproblem
// hasn't been solved yet
for(let i=0;i<100;i++)
{
dp[i]=new Array(100);
for(let j=0;j<100;j++)
{
dp[i][j]=new Array(100);
for(let k=0;k<100;k++)
{
dp[i][j][k]=-1;
}
}
}
// Function to calculate maximum score
function MaximumScoreDP(l,r,prefix_sum,num)
{
// Bse case
if (l > r)
return 0;
// If the same state has
// already been computed
if (dp[l][r][num] != -1)
return dp[l][r][num];
// Sum of array in range (l, r)
let current_sum
= prefix_sum[r]
- (l - 1 >= 0
? prefix_sum[l - 1]
: 0);
// If the operation is even-numbered
// the score is decremented
if (num % 2 == 0)
current_sum *= -1;
// Exploring all paths, and storing
// maximum value in DP table to avoid
// further repetitive recursive calls
dp[l][r][num] = current_sum
+ Math.max(
MaximumScoreDP(
l + 1, r,
prefix_sum,
num + 1),
MaximumScoreDP(
l, r - 1,
prefix_sum,
num + 1));
return dp[l][r][num];
}
// Function to find the max score
function findMaxScore(a,n)
{
// Prefix sum array
let prefix_sum = new Array(n);
prefix_sum[0] = a[0];
// Calculating prefix_sum
for (let i = 1; i < n; i++) {
prefix_sum[i]
= prefix_sum[i - 1] + a[i];
}
// Initialising the DP table,
// -1 represents the subproblem
// hasn't been solved yet
return MaximumScoreDP(
0, n - 1,
prefix_sum, 1);
}
// Driver code
let n = 6;
let A=[1, 2, 3, 4, 2, 6 ];
document.write(findMaxScore(A, n));
// This code is contributed by rag2127
</script>
Producción:
13
Complejidad temporal: O(N 3 )