Suma máxima de elementos incluso indexados obtenidos por desplazamiento a la derecha en un subarreglo de tamaño uniforme

Dada una array arr[] , necesitamos encontrar la suma máxima de los elementos indexados pares que se pueden obtener realizando la operación de desplazamiento a la derecha en cualquier subarreglo de longitud par por 1.
Ejemplos: 
 

Entrada: arr[] = {5, 1, 3, 4, 5, 6} 
Salida: 15 
Explicación: 
Podemos realizar un desplazamiento a la derecha en el índice 2 a 5, entonces la array resultante es: 
arr[] = {5, 1, 6 , 3, 4, 5} 
Suma de elementos en índices pares = 5 + 6 + 4 = 15
Entrada: arr[] = {7, 9, 1, 8, 3, 10, 4, 12} 
Salida: 39 
Explicación: 
Nosotros puede realizar un desplazamiento a la derecha en el índice 0 a 7, entonces la array resultante es: 
arr[] = {12, 7, 9, 1, 8, 3, 10, 4} 
Suma de elementos en índices pares = 12 + 9 + 8 + 10 = 39 
 

Enfoque ingenuo: el enfoque ingenuo consiste en desplazar a la derecha todos los subarreglos posibles de longitud uniforme en uno y encontrar la suma de los elementos en un índice uniforme para todo el arreglo formado después de cada posible cambio de subarreglo. La suma máxima en toda la array es el resultado requerido.
Complejidad de tiempo: O(N ² ) 
Espacio auxiliar: O(1) 
Enfoque eficiente: Para optimizar el enfoque ingenuo anterior, podemos observar que después de realizar el desplazamiento a la derecha en cualquier subarreglo par por 1, el valor del índice impar se reemplaza por el valor del índice par y viceversa. Si encontramos la suma del elemento en índices pares (digamos suma) antes del cambio, luego, después del cambio, la suma cambia por la suma de la diferencia consecutiva entre los elementos en el índice par e impar. 
Por ejemplo: 
 

arr[] = {1, 2, 3, 4} 
Elemento de suma en el índice par en la array anterior = 1 + 3 = 4  Desplace la
array a la derecha en 1, tenemos 
arr1[] = {4, 1, 2, 3} 
Suma elemento en el índice par en la array anterior = 4 + 2 = 6 
, por lo tanto, la suma difiere en 2 en las dos arrays anteriores, que es igual a la suma de la diferencia consecutiva en arr[] como ((2 – 1) + (4 – 3) ) = 2. 
 

Usaremos los conceptos anteriores para resolver este problema. A continuación se muestran los pasos:
 

1. Cree dos arrays (digamos arr1[] y arr2[] ) de modo que arr1[] almacene la diferencia consecutiva del elemento en la array arr[] como: 
    

{(a[1] – a[0]), (a[3] – a[2]), . . ., (a[n]-a[n-1])}

1. Y arr2[] almacenará la diferencia consecutiva del elemento en la array arr[] como: 
    

{(a[1] – a[2]), (a[3] – a[4]), . . ., (a[n-1]-a[n])}

1.  
2. Luego encuentre la suma máxima de subarreglo usando el Algoritmo de Kadane en los dos arreglos anteriores formados.
3. Ahora, la suma máxima es la suma del elemento en índices pares en la array original ( arr[] ) + suma máxima de subarreglo de las dos arrays arr1[] y arr2[] .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Kadane's Algorithm to find
// the maximum sum sub array
int kadane(vector<int> v)
{
    int maxSoFar = 0;
    int maxEndingHere = 0;
 
    // Iterate array v
    for (int i = 0; i < v.size(); i++) {
 
        maxEndingHere += v[i];
 
        // Update the maximum
        maxSoFar = max(maxEndingHere,
                    maxSoFar);
 
        // Update maxEndingHere to 0 if it
        // is less than 0
        maxEndingHere
            = max(maxEndingHere, 0);
    }
 
    // Return maximum sum
    return maxSoFar;
}
 
// Function to find the sum
// of even indexed elements
// after modification in array.
int sumOfElements(int* arr, int n)
{
    int sum = 0;
 
    // Find initial sum of
    // even indexed elements
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0)
            sum += arr[i];
    }
 
    // Create two vectors to store
    // the consecutive differences
    // of elements
    vector<int> v1;
    vector<int> v2;
 
    for (int i = 1; i < n; i += 2) {
 
        v1.push_back(arr[i]
                    - arr[i - 1]);
 
        if (i + 1 < n) {
            v2.push_back(arr[i]
                        - arr[i + 1]);
        }
    }
 
    // Find the maximum sum subarray
    int option1 = kadane(v1);
    int option2 = kadane(v2);
 
    // Add the maximum value
    // to initial sum
    int ans = sum + max(option1,
                        option2);
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 5, 1, 3, 4, 5, 6 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << sumOfElements(arr, N);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Kadane's Algorithm to find
// the maximum sum sub array
static int kadane(Vector<Integer> v)
{
    int maxSoFar = 0;
    int maxEndingHere = 0;
 
    // Iterate array v
    for(int i = 0; i < v.size(); i++)
    {
    maxEndingHere += v.get(i);
         
    // Update the maximum
    maxSoFar = Math.max(maxEndingHere,
                        maxSoFar);
         
    // Update maxEndingHere to 0 if it
    // is less than 0
    maxEndingHere = Math.max(maxEndingHere, 0);
    }
     
    // Return maximum sum
    return maxSoFar;
}
 
// Function to find the sum
// of even indexed elements
// after modification in array.
static int sumOfElements(int []arr, int n)
{
    int sum = 0;
 
    // Find initial sum of
    // even indexed elements
    for(int i = 0; i < n; i++)
    {
    if (i % 2 == 0)
        sum += arr[i];
    }
 
    // Create two vectors to store
    // the consecutive differences
    // of elements
    Vector<Integer> v1 = new Vector<Integer>();
    Vector<Integer> v2 = new Vector<Integer>();
 
    for(int i = 1; i < n; i += 2)
    {
    v1.add(arr[i] - arr[i - 1]);
         
    if (i + 1 < n)
    {
        v2.add(arr[i] - arr[i + 1]);
    }
    }
     
    // Find the maximum sum subarray
    int option1 = kadane(v1);
    int option2 = kadane(v2);
 
    // Add the maximum value
    // to initial sum
    int ans = sum + Math.max(option1,
                            option2);
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array arr[]
    int arr[] = { 5, 1, 3, 4, 5, 6 };
 
    int N = arr.length;
 
    // Function Call
    System.out.print(sumOfElements(arr, N));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Kadane's Algorithm to find
# the maximum sum sub array
def kadane(v):
 
    maxSoFar = 0;
    maxEndingHere = 0;
 
    # Iterate array v
    for i in range(len(v)):
        maxEndingHere += v[i];
 
        # Update the maximum
        maxSoFar = max(maxEndingHere,
                    maxSoFar);
 
        # Update maxEndingHere to 0
        # if it is less than 0
        maxEndingHere = max(maxEndingHere, 0);
 
    # Return maximum sum
    return maxSoFar;
 
# Function to find the sum
# of even indexed elements
# after modification in array.
def sumOfElements(arr, n):
 
    sum = 0;
 
    # Find initial sum of
    # even indexed elements
    for i in range(n):
        if (i % 2 == 0):
            sum += arr[i];
 
    # Create two vectors to store
    # the consecutive differences
    # of elements
    v1 = [];
    v2 = [];
 
    for i in range(1, n, 2):
        v1.append(arr[i] - arr[i - 1]);
 
        if (i + 1 < n):
            v2.append(arr[i] - arr[i + 1]);
 
    # Find the maximum sum subarray
    option1 = kadane(v1);
    option2 = kadane(v2);
 
    # Add the maximum value
    # to initial sum
    ans = sum + max(option1, option2);
 
    # Return the answer
    return ans;
 
# Driver Code
if __name__ == "__main__" :
 
    # Given array arr[]
    arr = [ 5, 1, 3, 4, 5, 6 ];
 
    N = len(arr);
 
    # Function call
    print(sumOfElements(arr, N));
 
# This code is contributed by AnkitRai01

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Kadane's Algorithm to find
// the maximum sum sub array
static int kadane(List<int> v)
{
    int maxSoFar = 0;
    int maxEndingHere = 0;
 
    // Iterate array v
    for(int i = 0; i < v.Count; i++)
    {
        maxEndingHere += v[i];
             
        // Update the maximum
        maxSoFar = Math.Max(maxEndingHere,
                            maxSoFar);
             
        // Update maxEndingHere to 0 if it
        // is less than 0
        maxEndingHere = Math.Max(maxEndingHere, 0);
    }
     
    // Return maximum sum
    return maxSoFar;
}
 
// Function to find the sum
// of even indexed elements
// after modification in array.
static int sumOfElements(int []arr, int n)
{
    int sum = 0;
 
    // Find initial sum of
    // even indexed elements
    for(int i = 0; i < n; i++)
    {
        if (i % 2 == 0)
            sum += arr[i];
    }
 
    // Create two vectors to store
    // the consecutive differences
    // of elements
    List<int> v1 = new List<int>();
    List<int> v2 = new List<int>();
 
    for(int i = 1; i < n; i += 2)
    {
        v1.Add(arr[i] - arr[i - 1]);
         
        if (i + 1 < n)
        {
            v2.Add(arr[i] - arr[i + 1]);
        }
    }
     
    // Find the maximum sum subarray
    int option1 = kadane(v1);
    int option2 = kadane(v2);
 
    // Add the maximum value
    // to initial sum
    int ans = sum + Math.Max(option1,
                             option2);
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []arr = { 5, 1, 3, 4, 5, 6 };
 
    int N = arr.Length;
 
    // Function call
    Console.Write(sumOfElements(arr, N));
}
}
 
// This code is contributed by Amit Katiyar

<script>
// Javascript program for the above approach
 
// Kadane's Algorithm to find
// the maximum sum sub array
function kadane(v)
{
    var maxSoFar = 0;
    var maxEndingHere = 0;
 
    // Iterate array v
    for (var i = 0; i < v.length; i++) {
 
        maxEndingHere += v[i];
 
        // Update the maximum
        maxSoFar = Math.max(maxEndingHere,maxSoFar);
 
        // Update maxEndingHere to 0 if it
        // is less than 0
        maxEndingHere = Math.max(maxEndingHere, 0);
    }
 
    // Return maximum sum
    return maxSoFar;
}
 
// Function to find the sum
// of even indexed elements
// after modification in array.
function sumOfElements(arr, n)
{
    var sum = 0;
 
    // Find initial sum of
    // even indexed elements
    for (var i = 0; i < n; i++) {
        if (i % 2 == 0)
            sum += arr[i];
    }
 
    // Create two vectors to store
    // the consecutive differences
    // of elements
    var v1 = [];
    var v2 = [];
 
    for (var i = 1; i < n; i += 2) {
 
        v1.push(arr[i] - arr[i - 1]);
 
        if (i + 1 < n) {
            v2.push(arr[i] - arr[i + 1]);
        }
    }
 
    // Find the maximum sum subarray
    var option1 = kadane(v1);
    var option2 = kadane(v2);
 
    // Add the maximum value
    // to initial sum
    var ans = sum + Math.max(option1,
                        option2);
 
    // Return the answer
    return ans;
}
 
 
var arr = [ 5, 1, 3, 4, 5, 6 ];
 
    var N = arr.length;
     
    // Function Call
    document.write(sumOfElements(arr, N));
 
// This code is contributed by SoumikMondal
</script>

15

Complejidad temporal: O(N)  
Espacio auxiliar: O(N)