Invierta un subarreglo del arreglo dado para minimizar la suma de elementos en una posición par

Dada una array arr[] de enteros positivos. La tarea es invertir un subarreglo para minimizar la suma de elementos en lugares pares e imprimir la suma mínima. 

Nota: Realice el movimiento solo una vez. Es posible que el subarreglo no se invierta. 

Ejemplo: 

Entrada: arr[] = {1, 2, 3, 4, 5} 
Salida: 7 
Explicación: 
Suma de elementos en posiciones pares inicialmente = arr[0] + arr[2] + arr[4] = 1 + 3 + 5 = 9 
Al invertir el subarreglo desde la posición [1, 4], el arreglo se convierte en: {1, 5, 4, 3, 2} 
Ahora la suma de elementos en posiciones pares = arr[0] + arr[2] + arr[ 4] = 1 + 4 + 2 = 7, que es la suma mínima. 

Entrada: arr[] = {0, 1, 4, 3} 
Salida: 1 
Explicación: 
Suma de elementos en posiciones pares inicialmente = arr[0] + arr[2] = 0 + 4 = 4 
Al invertir el subarreglo desde la posición [ 1, 2], la array se convierte en: {0, 4, 1, 3} 
Ahora la suma de elementos en posiciones pares = arr[0] + arr[2] = 0 + 1 = 1, que es la suma mínima. 
 

Enfoque ingenuo: la idea es aplicar el método de fuerza bruta y generar todo el subarreglo y verificar la suma de elementos en la posición par. Imprimir la suma que es el mínimo entre todos.

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

Enfoque eficiente: la idea es observar los siguientes puntos importantes para el arreglo arr[]:  

• Invertir el subarreglo de longitud impar no cambiará la suma porque todos los elementos en el índice par volverán a tener el índice par.
• Al invertir un subarreglo de longitud par , todos los elementos en la posición de índice pasarán al índice par y los elementos en el índice par pasarán al índice impar.
• La suma de elementos cambiará solo cuando un elemento de índice impar se coloque en elementos indexados pares. Digamos que el elemento en el índice 1 puede ir al índice 0 o al índice 2.
• Al pasar de un índice par a otro ejemplo de índice par del índice 2 al 4, estará cubriendo en el primer caso o si de índice impar a ejemplo de índice par del índice 1 al 4, estará cubriendo el segundo caso.

A continuación se muestran los pasos del enfoque basado en las observaciones anteriores:  

• Entonces, la idea es encontrar la suma de solo elementos de índice pares e inicializar dos arrays, digamos v1 y v2 , de modo que v1 mantendrá la cuenta del cambio si el primer elemento del índice va a 0, mientras que v2 mantendrá la cuenta del cambio si el primer elemento del índice va a 2.
• Obtenga el mínimo de los dos valores y verifique si es menor que 0. Si lo es, agréguelo a la respuesta y finalmente devuelva la respuesta.

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

// C++ implementation to reverse a subarray
// of the given array to minimize the
// sum of elements at even position
 
#include <bits/stdc++.h>
#define N 5
using namespace std;
 
// Function that will give
// the max negative value
int after_rev(vector<int> v)
{
    int mini = 0, count = 0;
 
    for (int i = 0; i < v.size(); i++) {
        count += v[i];
 
        // Check for count
        // greater than 0
        // as we require only
        // negative solution
        if (count > 0)
            count = 0;
 
        if (mini > count)
            mini = count;
    }
 
    return mini;
}
 
// Function to print the minimum sum
void print(int arr[N])
{
    int sum = 0;
 
    // Taking sum of only
    // even index elements
    for (int i = 0; i < N; i += 2)
        sum += arr[i];
 
    // Initialize two vectors v1, v2
    vector<int> v1, v2;
 
    // v1 will keep account for change
    // if 1th index element goes to 0
    for (int i = 0; i + 1 < N; i += 2)
        v1.push_back(arr[i + 1] - arr[i]);
 
    // v2 will keep account for change
    // if 1th index element goes to 2
    for (int i = 1; i + 1 < N; i += 2)
        v2.push_back(arr[i] - arr[i + 1]);
 
    // Get the max negative value
    int change = min(after_rev(v1),
                     after_rev(v2));
    if (change < 0)
        sum += change;
 
    cout << sum << endl;
}
 
// Driver code
int main()
{
 
    int arr[N] = { 0, 1, 4, 3 };
    print(arr);
    return 0;
}

// Java implementation to reverse a subarray
// of the given array to minimize the
// sum of elements at even position
import java.util.*;
 
class GFG{
 
static final int N = 5;
 
// Function that will give
// the max negative value
static int after_rev(Vector<Integer> v)
{
    int mini = 0, count = 0;
     
    for(int i = 0; i < v.size(); i++)
    {
        count += v.get(i);
 
        // Check for count greater
        // than 0 as we require only
        // negative solution
        if (count > 0)
            count = 0;
 
        if (mini > count)
            mini = count;
    }
    return mini;
}
 
// Function to print the minimum sum
static void print(int arr[])
{
    int sum = 0;
 
    // Taking sum of only
    // even index elements
    for(int i = 0; i < N; i += 2)
        sum += arr[i];
 
    // Initialize two vectors v1, v2
    Vector<Integer> v1, v2;
    v1 = new Vector<Integer>();
    v2 = new Vector<Integer>();
     
    // v1 will keep account for change
    // if 1th index element goes to 0
    for(int i = 0; i + 1 < N; i += 2)
        v1.add(arr[i + 1] - arr[i]);
 
    // v2 will keep account for change
    // if 1th index element goes to 2
    for(int i = 1; i + 1 < N; i += 2)
        v2.add(arr[i] - arr[i + 1]);
 
    // Get the max negative value
    int change = Math.min(after_rev(v1),
                          after_rev(v2));
    if (change < 0)
        sum += change;
 
    System.out.print(sum + "\n");
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 0, 1, 4, 3, 0 };
    print(arr);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation to reverse
# a subarray of the given array to
# minimize the sum of elements at
# even position
 
# Function that will give
# the max negative value
def after_rev(v):
 
    mini = 0
    count = 0
 
    for i in range(len(v)):
        count += v[i]
 
        # Check for count greater
        # than 0 as we require only
        # negative solution
        if(count > 0):
            count = 0
 
        if(mini > count):
            mini = count
 
    return mini
 
# Function to print the
# minimum sum
def print_f(arr):
 
    sum = 0
 
    # Taking sum of only
    # even index elements
    for i in range(0, len(arr), 2):
        sum += arr[i]
 
    # Initialize two vectors v1, v2
    v1, v2 = [], []
 
    # v1 will keep account for change
    # if 1th index element goes to 0
    i = 1
    while i + 1 < len(arr):
        v1.append(arr[i + 1] - arr[i])
        i += 2
 
    # v2 will keep account for change
    # if 1th index element goes to 2
    i = 1
    while i + 1 < len(arr):
        v2.append(arr[i] - arr[i + 1])
        i += 2
 
    # Get the max negative value
    change = min(after_rev(v1),
                 after_rev(v2))
 
    if(change < 0):
        sum += change
 
    print(sum)
 
# Driver code
if __name__ == '__main__':
 
    arr = [ 0, 1, 4, 3 ]
     
    print_f(arr)
 
# This code is contributed by Shivam Singh

// C# implementation to reverse a subarray
// of the given array to minimize the
// sum of elements at even position
using System;
using System.Collections.Generic;
class GFG{
 
static readonly int N = 5;
 
// Function that will give
// the max negative value
static int after_rev(List<int> v)
{
    int mini = 0, count = 0;
     
    for(int i = 0; i < v.Count; i++)
    {
        count += v[i];
 
        // Check for count greater
        // than 0 as we require only
        // negative solution
        if (count > 0)
            count = 0;
 
        if (mini > count)
            mini = count;
    }
    return mini;
}
 
// Function to print the minimum sum
static void print(int []arr)
{
    int sum = 0;
 
    // Taking sum of only
    // even index elements
    for(int i = 0; i < N; i += 2)
        sum += arr[i];
 
    // Initialize two vectors v1, v2
    List<int> v1, v2;
    v1 = new List<int>();
    v2 = new List<int>();
     
    // v1 will keep account for change
    // if 1th index element goes to 0
    for(int i = 0; i + 1 < N; i += 2)
        v1.Add(arr[i + 1] - arr[i]);
 
    // v2 will keep account for change
    // if 1th index element goes to 2
    for(int i = 1; i + 1 < N; i += 2)
        v2.Add(arr[i] - arr[i + 1]);
 
    // Get the max negative value
    int change = Math.Min(after_rev(v1),
                          after_rev(v2));
    if (change < 0)
        sum += change;
 
    Console.Write(sum + "\n");
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 0, 1, 4, 3, 0 };
    print(arr);
}
}
 
// This code is contributed by sapnasingh4991

<script>
 
// Javascript implementation to reverse a subarray
// of the given array to minimize the
// sum of elements at even position
 
var N = 3;
 
// Function that will give
// the max negative value
function after_rev(v)
{
    var mini = 0, count = 0;
 
    for (var i = 0; i < v.length; i++) {
        count += v[i];
 
        // Check for count
        // greater than 0
        // as we require only
        // negative solution
        if (count > 0)
            count = 0;
 
        if (mini > count)
            mini = count;
    }
 
    return mini;
}
 
// Function to print the minimum sum
function print(arr)
{
    var sum = 0;
 
    // Taking sum of only
    // even index elements
    for (var i = 0; i < N; i += 2)
        sum += arr[i];
 
    // Initialize two vectors v1, v2
    var v1 = [], v2 = [];
 
    // v1 will keep account for change
    // if 1th index element goes to 0
    for (var i = 0; i + 1 < N; i += 2)
        v1.push(arr[i + 1] - arr[i]);
 
    // v2 will keep account for change
    // if 1th index element goes to 2
    for (var i = 1; i + 1 < N; i += 2)
        v2.push(arr[i] - arr[i + 1]);
 
    // Get the max negative value
    var change = Math.min(after_rev(v1),
                     after_rev(v2));
    if (change < 0)
        sum += change;
 
    document.write( sum );
}
 
// Driver code
var arr = [0, 1, 4, 3];
print(arr);
 
// This code is contributed by importantly.
</script>

1

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