Maximizar la suma de diferencias consecutivas en una array circular

Dada una array de n elementos. Considere la array como una array circular, es decir, el elemento después de una _n es un ₁ . La tarea es encontrar la suma máxima de la diferencia entre elementos consecutivos con la reorganización del elemento de la array permitida, es decir, después de la reorganización del elemento, encuentre |a ₁ – a ₂ | + |a ₂ – a ₃ | + …… + |una _{norte – 1} – una _norte | + |una _n – una ₁ |. 

Ejemplos: 

Input : arr[] = { 4, 2, 1, 8 }
Output : 18
Rearrange given array as : { 1, 8, 2, 4 }
Sum of difference between consecutive element
= |1 - 8| + |8 - 2| + |2 - 4| + |4 - 1|
= 7 + 6 + 2 + 3
= 18.

Input : arr[] = { 10, 12, 15 }
Output : 10

La idea es usar Greedy Approach y tratar de acercar los elementos que tienen una mayor diferencia. 
Considere la permutación ordenada de la array dada a ₁ , a ₁ , a ₂ ,…., a _{n – 1} , a _n tal que a ₁ < a ₂ < a ₃ …. < un _{norte – 1} < un _norte . 
Ahora, para obtener la respuesta con la máxima suma de diferencias entre elementos consecutivos, organice los elementos de la siguiente manera: 
a ₁ , a _n , a ₂ , a _n-1 ,…., a _n/2 , a _{(n/2) + 1} 
Podemos observar que el arreglo produce la respuesta óptima, ya que todos los a ₁ , a ₂ , a ₃ ,….., a _(n/2)-1 , a _n/2 se restan dos veces mientras que a _{(n/2)+ 1} , a _(n/2)+2 , a _(n/2)+3 ,….., a _{n – 1} , a _n se suman dos veces. 

Nota:  a _(n/2)+1 Este término se considera solo para n pares porque para n impares, se suma una vez y se resta una vez y, por lo tanto, se cancela. 

Implementación:

// C++ program to maximize the sum of difference
// between consecutive elements in circular array
#include <bits/stdc++.h>
using namespace std;
 
// Return the maximum Sum of difference between
// consecutive elements.
int maxSum(int arr[], int n)
{
    int sum = 0;
 
    // Sorting the array.
    sort(arr, arr + n);
 
    // Subtracting a1, a2, a3,....., a(n/2)-1, an/2
    // twice and adding a(n/2)+1, a(n/2)+2, a(n/2)+3,.
    // ...., an - 1, an twice.
    for (int i = 0; i < n/2; i++)
    {
        sum -= (2 * arr[i]);
        sum += (2 * arr[n - i - 1]);
    }
 
    return sum;
}
 
// Driver Program
int main()
{
    int arr[] = { 4, 2, 1, 8 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << maxSum(arr, n) << endl;
    return 0;
}

// Java program to maximize the sum of difference
// between consecutive elements in circular array
import java.io.*;
import java.util.Arrays;
  
class MaxSum
{
    // Return the maximum Sum of difference between
    // consecutive elements.
    static int maxSum(int arr[], int n)
    {
        int sum = 0;
  
        // Sorting the array.
        Arrays.sort(arr);
      
        // Subtracting a1, a2, a3,....., a(n/2)-1,
        // an/2 twice and adding a(n/2)+1, a(n/2)+2,
        // a(n/2)+3,....., an - 1, an twice.
        for (int i = 0; i < n/2; i++)
        {
            sum -= (2 * arr[i]);
            sum += (2 * arr[n - i - 1]);
        }
      
        return sum;
    }
 
    // Driver Program
    public static void main (String[] args)
    {
        int arr[] = { 4, 2, 1, 8 };
        int n = arr.length;
        System.out.println(maxSum(arr, n));
    }
}
/*This code is contributed by Prakriti Gupta*/

# Python3 program to maximize the sum of difference
# between consecutive elements in circular array
 
# Return the maximum Sum of difference
# between consecutive elements
def maxSum(arr, n):
    sum = 0
 
    # Sorting the array
    arr.sort()
 
    # Subtracting a1, a2, a3,....., a(n/2)-1, an/2
    # twice and adding a(n/2)+1, a(n/2)+2, a(n/2)+3,.
    # ...., an - 1, an twice.
    for i in range(0, int(n / 2)) :
        sum -= (2 * arr[i])
        sum += (2 * arr[n - i - 1])
 
    return sum
 
 
# Driver Program
arr = [4, 2, 1, 8]
n = len(arr)
print (maxSum(arr, n))
 
# This code is contributed by Shreyanshi Arun.

// C# program to maximize the sum of difference
// between consecutive elements in circular array
using System;
 
class MaxSum {
     
    // Return the maximum Sum of difference
    // between consecutive elements.
    static int maxSum(int[] arr, int n)
    {
        int sum = 0;
 
        // Sorting the array.
        Array.Sort(arr);
 
        // Subtracting a1, a2, a3, ....., a(n/2)-1,
        // an/2 twice and adding a(n/2)+1, a(n/2)+2,
        // a(n/2)+3, ....., an - 1, an twice.
        for (int i = 0; i < n / 2; i++) {
            sum -= (2 * arr[i]);
            sum += (2 * arr[n - i - 1]);
        }
 
        return sum;
    }
 
    // Driver Program
    public static void Main()
    {
        int[] arr = { 4, 2, 1, 8 };
        int n = arr.Length;
        Console.WriteLine(maxSum(arr, n));
    }
}
 
//This Code is contributed by vt_m.

<script>
 
// JavaScript program for the above approach
 
    // Return the maximum Sum of difference between
    // consecutive elements.
    function maxSum(arr, n)
    {
        let sum = 0;
  
        // Sorting the array.
        arr.sort();
      
        // Subtracting a1, a2, a3,....., a(n/2)-1,
        // an/2 twice and adding a(n/2)+1, a(n/2)+2,
        // a(n/2)+3,....., an - 1, an twice.
        for (let i = 0; i < n/2; i++)
        {
            sum -= (2 * arr[i]);
            sum += (2 * arr[n - i - 1]);
        }
      
        return sum;
    }
 
// Driver Code
    let arr = [ 4, 2, 1, 8 ];
    let n = arr.length;
    document.write(maxSum(arr, n));
 
// This code is contributed by chinmoy1997pal.
</script>

18

Complejidad de tiempo: O (nlogn). 
Espacio Auxiliar : O(1)

Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.