Divida una array ordenada en K partes con la suma de la diferencia de máximo y mínimo minimizada en cada parte – Part 1

Dada una array ordenada ascendente arr[] de tamaño N y un número entero K , la tarea es dividir la array dada en K subarreglos no vacíos de modo que la suma de las diferencias del máximo y el mínimo de cada subarreglo se minimice.

Ejemplos: 

Entrada: arr[] = {4, 8, 15, 16, 23, 42}, K = 3 
Salida: 12 
Explicación: 
La array dada se puede dividir en tres sub-arrays de la siguiente manera: 
{4, 8}, { 15, 16, 23}, {42} 
Aquí, la suma de la diferencia del elemento mínimo y máximo en cada uno de los subarreglos respectivamente son: 
4 + 8 + 0 = 12.

Entrada: arr[] = {1, 2, 3, 4, 5}, K = 5 
Salida: 0 

Enfoque: una observación que debe hacerse es que sabemos claramente que la suma de la diferencia entre el elemento máximo y mínimo del subarreglo es mínima solo cuando elegimos los elementos adyacentes como el elemento máximo y mínimo del subarreglo. Asi que: 

• Digamos que tenemos que dividir la array en K + 1 partes, de modo que la primera parte sea arr[0 … i ₁ -1], la segunda parte sea arr[i ₁ … i ₂ -1], y así sucesivamente.
• Entonces, la suma de las diferencias entre las K partes será:

suma = arr[i ₁ -1] – arr[0] + arr[i ₂ -1] – arr[i ₁ ] + …. + arr[n] – arr[i _K ] 
 

• Después de reorganizar el valor anterior, obtenemos:

suma = -arr[0] – (arr[i ₁ ] – arr[i ₁ – 1]) – (arr[i ₂ ] – arr[i ₂ – 1]) – … -(arr[i _K ] – arr [i _K – 1]) + arr[N – 1] 
 

• Claramente, el valor a calcular se forma a partir de la diferencia entre los elementos adyacentes de la array. Si esta diferencia es máxima, entonces la suma será mínima.
• Por lo tanto, la idea es iterar sobre la array y almacenar la diferencia entre los elementos adyacentes de la array en otra array.
• Ahora, ordene esta array en orden descendente. Sabemos que se deben tomar los valores máximos de la diferencia para obtener la diferencia mínima.
• Por lo tanto, reste los primeros valores K – 1 de la diferencia del primer y último elemento de la array. Esto da la suma de las diferencias restantes de los K subarreglos formados a partir del arreglo.

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

// C++ program to find the minimum
// sum of differences possible for
// the given array when the array
// is divided into K subarrays
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// sum of differences possible for
// the given array when the array
// is divided into K subarrays
int calculate_minimum_split(int n, int a[], int k)
{
 
    // Array to store the differences
    // between two adjacent elements
    int p[n - 1];
     
    // Iterating through the array
    for(int i = 1; i < n; i++)
     
        // Storing differences to p
        p[i - 1] = a[i] - a[i - 1];
         
    // Sorting p in descending order
    sort(p, p + n - 1, greater<int>());
     
    // Sum of the first k-1 values of p
    int min_sum = 0;
    for(int i = 0; i < k - 1; i++)
        min_sum += p[i];
         
    // Computing the result
    int res = a[n - 1] - a[0] - min_sum;
     
    return res;
}
 
// Driver code
int main()
{
    int arr[6] = { 4, 8, 15, 16, 23, 42 };
    int k = 3;
    int n = sizeof(arr) / sizeof(int);
 
    cout << calculate_minimum_split(n, arr, k);
}
 
// This code is contributed by ishayadav181

// Java program to find the minimum
// sum of differences possible for
// the given array when the array
// is divided into K subarrays
import java.util.*;
 
class GFG{
 
// Function to find the minimum
// sum of differences possible for
// the given array when the array
// is divided into K subarrays
static int calculate_minimum_split(int n, int a[],
                                   int k)
{
     
    // Array to store the differences
    // between two adjacent elements
    Integer[] p = new Integer[n - 1];
 
    // Iterating through the array
    for(int i = 1; i < n; i++)
 
        // Storing differences to p
        p[i - 1] = a[i] - a[i - 1];
 
    // Sorting p in descending order
    Arrays.sort(p, new Comparator<Integer>()
    {
        public int compare(Integer a, Integer b)
        {
            return b - a;
        }
    });
 
    // Sum of the first k-1 values of p
    int min_sum = 0;
    for(int i = 0; i < k - 1; i++)
        min_sum += p[i];
 
    // Computing the result
    int res = a[n - 1] - a[0] - min_sum;
 
    return res;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 4, 8, 15, 16, 23, 42 };
    int k = 3;
    int n = arr.length;
 
    System.out.println(calculate_minimum_split(
                       n, arr, k));
}
}
 
// This code is contributed by offbeat

# Python3 program to find the minimum
# sum of differences possible for
# the given array when the array
# is divided into K subarrays
 
# Function to find the minimum
# sum of differences possible for
# the given array when the array
# is divided into K subarrays
def calculate_minimum_split(a, k):
 
    # Array to store the differences
    # between two adjacent elements
    p =[]
    n = len(a)
 
    # Iterating through the array
    for i in range(1, n):
         
        # Appending differences to p
        p.append(a[i]-a[i-1])
 
    # Sorting p in descending order
    p.sort(reverse = True)
  
    # Sum of the first k-1 values of p
    min_sum = sum(p[:k-1])
  
    # Computing the result
    res = a[n-1]-a[0]-min_sum
     
    return res
 
if __name__ == "__main__":
    arr = [4, 8, 15, 16, 23, 42]
    K = 3
 
    print(calculate_minimum_split(arr, K))

// C# program to find the minimum 
// sum of differences possible for 
// the given array when the array 
// is divided into K subarrays 
using System;
 
class GFG{
     
// Function to find the minimum 
// sum of differences possible for 
// the given array when the array 
// is divided into K subarrays 
static int calculate_minimum_split(int n, int[] a,
                                   int k) 
{ 
     
    // Array to store the differences 
    // between two adjacent elements 
    int[] p = new int[n - 1]; 
       
    // Iterating through the array 
    for(int i = 1; i < n; i++) 
       
        // Storing differences to p 
        p[i - 1] = a[i] - a[i - 1]; 
           
    // Sorting p in descending order 
    Array.Sort(p);
    Array.Reverse(p);
       
    // Sum of the first k-1 values of p 
    int min_sum = 0; 
    for(int i = 0; i < k - 1; i++) 
        min_sum += p[i]; 
           
    // Computing the result 
    int res = a[n - 1] - a[0] - min_sum; 
       
    return res; 
} 
 
// Driver code
static void Main()
{
    int[] arr = { 4, 8, 15, 16, 23, 42 }; 
    int k = 3; 
    int n = arr.Length; 
 
    Console.Write(calculate_minimum_split(
                  n, arr, k));
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
// Javascript program to find the minimum
// sum of differences possible for
// the given array when the array
// is divided into K subarrays
 
 
// Function to find the minimum
// sum of differences possible for
// the given array when the array
// is divided into K subarrays
function calculate_minimum_split(n, a, k)
{
      
    // Array to store the differences
    // between two adjacent elements
    let p = Array.from({length: n-1}, (_, i) => 0);
        
    // Iterating through the array
    for(let i = 1; i < n; i++)
        
        // Storing differences to p
        p[i - 1] = a[i] - a[i - 1];
            
    // Sorting p in descending order
    p.sort((a, b) => a - b);
    p.reverse();
        
    // Sum of the first k-1 values of p
    let min_sum = 0;
    for(let i = 0; i < k - 1; i++)
        min_sum += p[i];
            
    // Computing the result
    let res = a[n - 1] - a[0] - min_sum;
        
    return res;
}
 
// Driver Code
     
       let arr = [ 4, 8, 15, 16, 23, 42 ];
    let k = 3;
    let n = arr.length;
  
    document.write(calculate_minimum_split(
                       n, arr, k));
   
            
</script>

12

Complejidad de tiempo: O(N * log(N)) , donde N es el tamaño de la array.

Espacio Auxiliar: O(N)