Dada una array arr[] de tamaño N , la tarea es maximizar la diferencia de la suma de elementos en índices pares y elementos en índices impares desplazando cualquier subarreglo de longitud impar al final de la array.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5, 6}
Salida: 3
Explicación : Inicialmente suma de elementos en índices pares = 1 + 3 + 5 = 9
Suma de elementos en índices impares = 2 + 4 + 6 = 12
Diferencia = 9 -12 = -3
Al desplazar el subarreglo de [0, 2] al final, el arreglo se convierte en {4, 5, 6, 1, 2, 3}
Suma de elementos en índices pares = 4 + 6 + 2 = 12
Suma de elementos con índices impares = 5 + 1 + 3 = 9
Diferencia = 12 – 9 = 3
Esto da la respuesta máxima de todos esos cambios que es igual a 3.Entrada: arr[] = {3, 4, 8}
Salida: 7
Enfoque : la tarea se puede resolver matemáticamente, utilizando la técnica de la suma de prefijos . El problema se puede dividir en 4 casos:
Caso 1 : cuando la longitud del arreglo N es par y l (inicio del subarreglo) es par {a,b,c,d,e,f} para l = 2, r =4 (indexación basada en uno)
Inicial: +a – b + c – d + e -f al desplazar el subconjunto de [2,4] hasta el final, el conjunto se convierte en = {a, e, f, b, c, d}
Final: + a- e +f – b + cd
Al sumergir la array en 3 subpartes [1, l), [l, r], (r, N).
El signo de la parte 1 [1, l) permanece igual, la parte 2 [l, r] permanece igual y la parte 3 ( r, N] se vuelve negativo (signo opuesto) después del cambio.
Si se calcula la array prefix_sum, entonces la suma después del cambio se convierte en
suma1 = suma_prefijo(l-1) + ( suma_prefijo(r) – suma_prefijo(l-1) ) – ((suma_prefijo(n) – suma_prefijo(r))
suma1 = 2* suma_prefijo(r) – suma_prefijo(N)Caso 2 : cuando la longitud del arreglo N es par y l (inicio del subarreglo) es impar {a, b, c, d, e, f} para l = 3, r = 5 (indexación basada en uno)
Inicial: +a – b + c – d + e -f al desplazar [3,5] al final la array se convierte en = {a, b, f, c, d, e}
Final: + a – b + f – c + d – e
Al sumergir la array en 3 subpartes [1, l), [l, r], (r, N).
El signo de la parte 1 [1, l) sigue siendo el mismo, la parte 2 [l, r] se convierte en signo opuesto y la parte 3 ( r, N] se convierte en signo opuesto después del cambio.
Si se calcula la array prefix_sum, entonces la suma después del cambio se convierte en
suma2 = suma_prefijo(l-1) – ( suma_prefijo(r) – suma_prefijo(l-1)) – ((suma_prefijo(n) – suma_prefijo(r))
suma2 = 2* suma_prefijo(l-1) – suma_prefijo(N)Caso 3 : cuando la longitud del arreglo N es impar y l (inicio del subarreglo) es par {a, b, c, d, e} para l = 2, r = 4 (indexación basada en uno)
Inicial: +a – b + c – d + e al desplazar el subconjunto de [2,4] hasta el final, el conjunto se convierte en = {a, e, b, c, d}
Final: + a – e + b – c + d
Al sumergir el conjunto a 3 subpartes [1, l) , [l, r] , (r, N] .
El signo de la parte 1 [1, l) sigue siendo el mismo, la parte 2 [l, r] se convierte en signo opuesto y la parte 3 (r, N) se convierte en negativo (signo opuesto) después del cambio.
Si se calcula la array prefix_sum, entonces la suma después del cambio se convierte en
suma3 = suma_prefijo(l-1) – (suma_prefijo(r) – suma_prefijo(l-1)) – ((suma_prefijo(n) – suma_prefijo(r))
suma3 = 2* suma_prefijo(l-1) – suma_prefijo(N)Caso 4 : cuando la longitud del arreglo N es impar y l (inicio del subarreglo) es impar {a, b, c, d, e} para l = 3, r = 3 (indexación basada en uno)
Inicial: +a – b + c – d + e al desplazar [3,5] hasta el final, la array se convierte en = {a, b, d, e, c}
Final: + a – b + d – e + c
Al dividir la array en 3 subpartes [1, l) , [l, r] , (r, N] .
El signo de part1 [1, l) sigue siendo el mismo, part2 [l, r] se convierte en signo opuesto y part3 (r, N] sigue siendo el mismo.
Si la array prefix_sum se calcula y luego la suma después del cambio se convierte en
sum4 = prefix_sum(l-1) + (prefix_sum(r) – prefix_sum(l-1)) – ((prefix_sum(n) – prefix_sum(r))
sum4 = 2* prefix_sum(r) – prefix_sum(N)
- Si n es par, el resultado se convierte en: max(sum1, sum2).
- Si n es impar, el resultado se convierte en: max(sum3,sum4).
Siga los pasos a continuación para resolver el problema:
- Inicialice un vector prefix_sum de tamaño n+1 con 0.
- Ahora modifique los índices impares de la array multiplicándolos por -1.
- Itere a través de la array en el rango [ 1, n] y complete el vector prefix_sum .
- Si el tamaño de la array es par
- Inicialice la variable maxval a -1e8 para almacenar la suma máxima.
- Iterar a través del vector de suma de prefijos y verificar
- Si incluso asigno maxval como max(maxval, 2 * prefix_sum[i] – prefix_sum[n]) .
- De lo contrario, asigne maxval como max(maxval, 2 * prefix_sum[i] – prefix_sum[n]) .
- Si el tamaño de la array es impar .
- Inicialice la variable maxval a -1e8 para almacenar la suma máxima.
- Iterar a través del vector de suma de prefijos y verificar
- Si incluso asigno maxval como max(maxval, 2 * prefix_sum[i – 1] – prefix_sum[n])
- De lo contrario, asigne maxval como max (maxval, 2 * prefix_sum [i] – prefix_sum [n])
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 find the maximum value of
// difference between sum of elements
// at even indices and sum of elements
// at odd indices by shifting
// a subarray of odd length to the
// end of the array
int find_maxsum(int arr[], int n)
{
vector<int> prefix_sum(n + 1, 0);
// Modify the array to keep
// alternative +ve and -ve
for (int i = 0; i < n; i++) {
if (i % 2 == 1) {
arr[i] = -arr[i];
}
}
// Function to find the prefix sum
for (int i = 1; i <= n; i++) {
prefix_sum[i] = prefix_sum[i - 1]
+ arr[i - 1];
}
// If n is even
if (n % 2 == 0) {
// Initialize the maxval to -1e8
int maxval = -1e8;
for (int i = 1; i <= n; i++) {
// If i is even (case-1)
if (i % 2 == 0) {
maxval = max(maxval, 2 *
prefix_sum[i]
- prefix_sum[n]);
}
// If i is odd (case-2)
else {
maxval = max(maxval, 2 *
prefix_sum[i - 1]
- prefix_sum[n]);
}
}
// return the maxval
return maxval;
}
else {
// Initialize the maxval to -1e8
int maxval = -1e8;
for (int i = 1; i <= n; i++) {
// If i is even (case 3)
if (i % 2 == 0) {
maxval = max(maxval, 2 *
prefix_sum[i - 1]
- prefix_sum[n]);
}
// If i is odd (case 4)
else {
maxval = max(maxval, 2 *
prefix_sum[i]
- prefix_sum[n]);
}
}
// Return the maxval
return maxval;
}
}
int main()
{
// Initialize an array
int arr[] = { 1, 2, 3, 4, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << find_maxsum(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to find the maximum value of
// difference between sum of elements
// at even indices and sum of elements
// at odd indices by shifting
// a subarray of odd length to the
// end of the array
static int find_maxsum(int arr[], int n)
{
int prefix_sum[] = new int[n + 1];
for(int i = 0; i < n + 1; i++) {
prefix_sum[i] = 0;
}
// Modify the array to keep
// alternative +ve and -ve
for (int i = 0; i < n; i++) {
if (i % 2 == 1) {
arr[i] = -arr[i];
}
}
// Function to find the prefix sum
for (int i = 1; i <= n; i++) {
prefix_sum[i] = prefix_sum[i - 1]
+ arr[i - 1];
}
// If n is even
if (n % 2 == 0) {
// Initialize the maxval to -1e8
int maxval = (int)-1e8;
for (int i = 1; i <= n; i++) {
// If i is even (case-1)
if (i % 2 == 0) {
maxval = Math.max(maxval, 2 *
prefix_sum[i]
- prefix_sum[n]);
}
// If i is odd (case-2)
else {
maxval = Math.max(maxval, 2 *
prefix_sum[i - 1]
- prefix_sum[n]);
}
}
// return the maxval
return maxval;
}
else
{
// Initialize the maxval to -1e8
int maxval = (int)-1e8;
for (int i = 1; i <= n; i++) {
// If i is even (case 3)
if (i % 2 == 0) {
maxval = Math.max(maxval, 2 *
prefix_sum[i - 1]
- prefix_sum[n]);
}
// If i is odd (case 4)
else {
maxval = Math.max(maxval, 2 *
prefix_sum[i]
- prefix_sum[n]);
}
}
// Return the maxval
return maxval;
}
}
public static void main(String args[])
{
// Initialize an array
int arr[] = { 1, 2, 3, 4, 5, 6 };
int N = arr.length;
// Function call
System.out.println(find_maxsum(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python program for the above approach # Function to find the maximum value of # difference between sum of elements # at even indices and sum of elements # at odd indices by shifting # a subarray of odd length to the # end of the array def find_maxsum(arr, n): prefix_sum = [ 0 for i in range(n + 1)] # Modify the array to keep # alternative +ve and -ve for i in range(n): if (i % 2 == 1): arr[i] = -arr[i] # Function to find the prefix sum for i in range(1, n+1): prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1] # If n is even if (n % 2 == 0): # Initialize the maxval to -1e8 maxval = -10**8 for i in range(1,n+1): # If i is even (case-1) if (i % 2 == 0): maxval = max(maxval, 2 * prefix_sum[i] - prefix_sum[n]) # If i is odd (case-2) else: maxval = max(maxval, 2 * prefix_sum[i - 1]- prefix_sum[n]) # return the maxval return maxval else: # Initialize the maxval to -1e8 maxval = -10**8 for i in range(1, n+1): # If i is even (case 3) if (i % 2 == 0): maxval = max(maxval, 2 * prefix_sum[i - 1] - prefix_sum[n]) # If i is odd (case 4) else: maxval = max(maxval, 2 * prefix_sum[i] - prefix_sum[n]) # Return the maxval return maxval # Initialize an array arr = [1, 2, 3, 4, 5, 6] N = len(arr) # Function call print(find_maxsum(arr, N)) # This code is contributed by Shubham Singh
C#
// C# code to implement the above approach
using System;
public class GFG{
// Function to find the maximum value of
// difference between sum of elements
// at even indices and sum of elements
// at odd indices by shifting
// a subarray of odd length to the
// end of the array
static int find_maxsum(int[] arr, int n)
{
int[] prefix_sum = new int[n + 1];
for(int i = 0; i < n + 1; i++) {
prefix_sum[i] = 0;
}
// Modify the array to keep
// alternative +ve and -ve
for (int i = 0; i < n; i++) {
if (i % 2 == 1) {
arr[i] = -arr[i];
}
}
// Function to find the prefix sum
for (int i = 1; i <= n; i++) {
prefix_sum[i] = prefix_sum[i - 1]
+ arr[i - 1];
}
// If n is even
if (n % 2 == 0) {
// Initialize the maxval to -1e8
int maxval = (int)-1e8;
for (int i = 1; i <= n; i++) {
// If i is even (case-1)
if (i % 2 == 0) {
maxval = Math.Max(maxval, 2 *
prefix_sum[i]
- prefix_sum[n]);
}
// If i is odd (case-2)
else {
maxval = Math.Max(maxval, 2 *
prefix_sum[i - 1]
- prefix_sum[n]);
}
}
// return the maxval
return maxval;
}
else
{
// Initialize the maxval to -1e8
int maxval = (int)-1e8;
for (int i = 1; i <= n; i++) {
// If i is even (case 3)
if (i % 2 == 0) {
maxval = Math.Max(maxval, 2 *
prefix_sum[i - 1]
- prefix_sum[n]);
}
// If i is odd (case 4)
else {
maxval = Math.Max(maxval, 2 *
prefix_sum[i]
- prefix_sum[n]);
}
}
// Return the maxval
return maxval;
}
}
// Driver code
public static void Main()
{
// Initialize an array
int[] arr = { 1, 2, 3, 4, 5, 6 };
int N = arr.Length;
// Function call
Console.Write(find_maxsum(arr, N));
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum value of
// difference between sum of elements
// at even indices and sum of elements
// at odd indices by shifting
// a subarray of odd length to the
// end of the array
function find_maxsum(arr, n)
{
let prefix_sum = new Array(n + 1).fill(0);
// Modify the array to keep
// alternative +ve and -ve
for (let i = 0; i < n; i++) {
if (i % 2 == 1) {
arr[i] = -arr[i];
}
}
// Function to find the prefix sum
for (let i = 1; i <= n; i++) {
prefix_sum[i] = prefix_sum[i - 1]
+ arr[i - 1];
}
// If n is even
if (n % 2 == 0) {
// Initialize the maxval to -1e8
let maxval = -1e8;
for (let i = 1; i <= n; i++) {
// If i is even (case-1)
if (i % 2 == 0) {
maxval = Math.max(maxval, 2 *
prefix_sum[i]
- prefix_sum[n]);
}
// If i is odd (case-2)
else {
maxval = Math.max(maxval, 2 *
prefix_sum[i - 1]
- prefix_sum[n]);
}
}
// return the maxval
return maxval;
}
else {
// Initialize the maxval to -1e8
let maxval = -1e8;
for (let i = 1; i <= n; i++) {
// If i is even (case 3)
if (i % 2 == 0) {
maxval = Math.max(maxval, 2 *
prefix_sum[i - 1]
- prefix_sum[n]);
}
// If i is odd (case 4)
else {
maxval = Math.max(maxval, 2 *
prefix_sum[i]
- prefix_sum[n]);
}
}
// Return the maxval
return maxval;
}
}
// Initialize an array
let arr = [1, 2, 3, 4, 5, 6];
let N = arr.length;
// Function call
document.write(find_maxsum(arr, N));
// This code is contributed by gfgking.
</script>
3
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar : O(N), ya que estamos usando espacio adicional para prefix_sum.
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA