Divida la array en K subarreglos de modo que la suma del máximo de todos los subarreglos se maximice

Dada una array arr[] de tamaño N y un número K , la tarea es dividir la array dada en K subarreglos contiguos de modo que la suma del máximo de cada subarreglo sea el máximo posible. Si es posible dividir la array de esa manera, imprima la suma máxima posible. De lo contrario, imprima » -1 «.

Ejemplos:

Entrada: arr[] = {5, 3, 2, 7, 6, 4}, N = 6, K = 3
Salida:  18
              5
              3 2 7
              6 4
Explicación:
una forma es dividir la array en los índices 0, 3 y 4.
Por lo tanto, los subarreglos formados son {5}, {3, 2, 7} y {6, 4}.
Por lo tanto, suma del máximo de cada subarreglo = 5 + 7 + 6 = 18 (que es el máximo posible).

Entrada: arr[] = {1, 4, 5, 6, 1, 2}, N = 6, K = 2 
Salida: 11

Enfoque: el problema dado se puede resolver utilizando la estructura de datos del mapa y las técnicas de clasificación , según las siguientes observaciones: 

• La suma máxima obtenible sería la suma de los K elementos más grandes de la array, ya que siempre es posible dividir la array en K segmentos de tal manera que el máximo de cada segmento sea uno de los K elementos más grandes.
• Una forma sería romper un segmento tan pronto como se encuentre uno de los elementos K más grandes .

Siga los pasos a continuación para resolver el problema:

• Primero, si N es menor que K , imprima » -1 » y luego regrese.
• Copie la array en otra array, diga temp[] y ordene la array, temp[] en orden descendente .
• Inicializar una variable ans a 0 , para almacenar la máxima suma posible.
• Además, inicialice un mapa , digamos mp , para almacenar la frecuencia de los elementos K más grandes .
• Itere en el rango [0, K-1] usando una variable, digamos i, y en cada iteración incremente el ans por temp[i] e incremente el conteo de temp[i] en el mapa mp.
• Inicialice un vector de vectores , digamos P , para almacenar una posible partición y un vector, digamos V , para almacenar los elementos de una partición.
• Itere en el rango [0, N-1] y usando una variable, diga i y realice los siguientes pasos:
  • Empuje el elemento actual arr[i] en el vector V .
  • Si mp[arr[i]] es mayor que 0 , haga lo siguiente:
    • Disminuya K y cuente arr[i] en el mapa mp en 1 .
    • Si K es igual a 0 , es decir, es el último segmento, inserte todos los elementos restantes de la array arr[] en V.
    • Ahora empuje el segmento actual V en la P .
• Finalmente, después de completar los pasos anteriores, imprima la suma máxima almacenada en la variable ans y luego divida el almacenamiento en P .

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

// C++ program for tha above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to split the array into K
// subarrays such that the sum of
// maximum of each subarray is maximized
void partitionIntoKSegments(int arr[],
                            int N, int K)
{
    // If N is less than K
    if (N < K) {
        cout << -1 << endl;
        return;
    }
    // Map to store the K
    // largest elements
    map<int, int> mp;
  
    // Auxiliary array to
    // store and sort arr[]
    int temp[N];
  
    // Stores the maximum sum
    int ans = 0;
  
    // Copy arr[] to temp[]
    for (int i = 0; i < N; i++) {
        temp[i] = arr[i];
    }
  
    // Sort array temp[] in
    // descending order
    sort(temp, temp + N,
         greater<int>());
  
    // Iterate in the range [0, K - 1]
    for (int i = 0; i < K; i++) {
  
        // Increment sum by temp[i]
        ans += temp[i];
  
        // Increment count of
        // temp[i] in the map mp
        mp[temp[i]]++;
    }
  
    // Stores the partitions
    vector<vector<int> > P;
  
    // Stores temporary subarrays
    vector<int> V;
  
    // Iterate over the range [0, N - 1]
    for (int i = 0; i < N; i++) {
        V.push_back(arr[i]);
  
        // If current element is
        // one of the K largest
        if (mp[arr[i]] > 0) {
  
            mp[arr[i]]--;
            K--;
  
            if (K == 0) {
                i++;
                while (i < N) {
                    V.push_back(arr[i]);
                    i++;
                }
            }
  
            if (V.size()) {
                P.push_back(V);
                V.clear();
            }
        }
    }
  
    // Print the ans
    cout << ans << endl;
  
    // Print the partition
    for (auto u : P) {
        for (auto x : u)
            cout << x << " ";
        cout << endl;
    }
}
// Driver code
int main()
{
    // Input
    int A[] = { 5, 3, 2, 7, 6, 4 };
    int N = sizeof(A) / sizeof(A[0]);
    int K = 3;
  
    // Function call
    partitionIntoKSegments(A, N, K);
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG
{
  
// Function to split the array into K
// subarrays such that the sum of
// maximum of each subarray is maximized
static void partitionIntoKSegments(int arr[], int N, int K)
{
      
    // If N is less than K
    if (N < K)
    {
         System.out.println(-1);
        return;
    }
      
    // Map to store the K
    // largest elements
    HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
  
    // Auxiliary array to
    // store and sort arr[]
    Integer []temp = new Integer[N];
  
    // Stores the maximum sum
    int ans = 0;
  
    // Copy arr[] to temp[]
    for(int i = 0; i < N; i++) 
    {
        temp[i] = arr[i];
    }
  
    // Sort array temp[] in
    // descending order
    Arrays.sort(temp,Collections.reverseOrder());
    //Array.Reverse(temp);
  
    // Iterate in the range [0, K - 1]
    for(int i = 0; i < K; i++) 
    {
          
        // Increment sum by temp[i]
        ans += temp[i];
  
        // Increment count of
        // temp[i] in the map mp
        if (mp.containsKey(temp[i]))
            mp.get(temp[i]++);
        else
            mp.put(temp[i], 1);
    }
  
    // Stores the partitions
    ArrayList<ArrayList<Integer>> P = new ArrayList<ArrayList<Integer>>();
  
    // Stores temporary subarrays
    ArrayList<Integer> V = new ArrayList<Integer>();
  
    // Iterate over the range [0, N - 1]
    for(int i = 0; i < N; i++)
    {
        V.add(arr[i]);
      
        // If current element is
        // one of the K largest
        if (mp.containsKey(arr[i]) && mp.get(arr[i]) > 0)
        {
            mp.get(arr[i]--);
            K--;
  
            if (K == 0)
            {
                i++;
                  
                while (i < N) 
                {
                    V.add(arr[i]);
                    i++;
                }
            }
  
            if (V.size() > 0)
            {
                P.add(new ArrayList<Integer>(V));
                V.clear();
            }
        }
    }
  
    // Print the ans
     System.out.println(ans);
      
    // Print the partition
    for (ArrayList<Integer > subList : P)
    {
        for(Integer  item : subList)
        {
              System.out.print(item+" ");
        }
         System.out.println();
    }
}
  
// Driver code
public static void main(String args[])
{
      
    // Input
    int []A = { 5, 3, 2, 7, 6, 4 };
    int N = A.length;
    int K = 3;
  
    // Function call
    partitionIntoKSegments(A, N, K);
}
}
  
// This code is contributed by SoumikMondal

# Python program for tha above approach
  
# Function to split the array into K
# subarrays such that the sum of
# maximum of each subarray is maximized
def partitionIntoKSegments(arr, N, K):
    # If N is less than K
    if (N < K):
        print(-1)
        return
    # Map to store the K
    # largest elements
    mp = {}
  
    # Auxiliary array to
    # store and sort arr[]
    temp = [0]*N
  
    # Stores the maximum sum
    ans = 0
  
    # Copy arr[] to temp[]
    for i in range(N):
        temp[i] = arr[i]
  
    # Sort array temp[] in
    # descending order
    temp = sorted(temp)[::-1]
  
    # Iterate in the range [0, K - 1]
    for i in range(K):
        # Increment sum by temp[i]
        ans += temp[i]
  
        # Increment count of
        # temp[i] in the map mp
        mp[temp[i]] = mp.get(temp[i], 0) + 1
  
    # Stores the partitions
    P = []
  
    # Stores temporary subarrays
    V = []
  
    # Iterate over the range [0, N - 1]
    for i in range(N):
        V.append(arr[i])
  
        # If current element is
        # one of the K largest
        if (arr[i] in mp):
  
            mp[arr[i]] -= 1
            K -= 1
  
            if (K == 0):
                i += 1
                while (i < N):
                    V.append(arr[i])
                    i += 1
            # print(V)
  
            if (len(V) > 0):
                P.append(list(V))
                V.clear()
  
    # Print ans
    print(ans)
  
    # Print partition
    for u in P:
        for x in u:
            print(x,end=" ")
        print()
# Driver code
if __name__ == '__main__':
    # Input
    A = [5, 3, 2, 7, 6, 4]
    N = len(A)
    K = 3
  
    # Function call
    partitionIntoKSegments(A, N, K)
  
# This code is contributed by mohit kumar 29.

// C# program for tha above approach
using System;
using System.Collections.Generic;
  
class GFG{
  
// Function to split the array into K
// subarrays such that the sum of
// maximum of each subarray is maximized
static void partitionIntoKSegments(int []arr,
                                   int N, int K)
{
      
    // If N is less than K
    if (N < K)
    {
        Console.WriteLine(-1);
        return;
    }
      
    // Map to store the K
    // largest elements
    Dictionary<int,
               int> mp = new Dictionary<int,
                                        int>();
  
    // Auxiliary array to
    // store and sort arr[]
    int []temp = new int[N];
  
    // Stores the maximum sum
    int ans = 0;
  
    // Copy arr[] to temp[]
    for(int i = 0; i < N; i++) 
    {
        temp[i] = arr[i];
    }
  
    // Sort array temp[] in
    // descending order
    Array.Sort(temp);
    Array.Reverse(temp);
  
    // Iterate in the range [0, K - 1]
    for(int i = 0; i < K; i++) 
    {
          
        // Increment sum by temp[i]
        ans += temp[i];
  
        // Increment count of
        // temp[i] in the map mp
        if (mp.ContainsKey(temp[i]))
            mp[temp[i]]++;
        else
            mp.Add(temp[i],1);
    }
  
    // Stores the partitions
    List<List<int>> P = new List<List<int>>();
  
    // Stores temporary subarrays
    List<int> V = new List<int>();
  
    // Iterate over the range [0, N - 1]
    for(int i = 0; i < N; i++)
    {
        V.Add(arr[i]);
      
        // If current element is
        // one of the K largest
        if (mp.ContainsKey(arr[i]) && mp[arr[i]] > 0)
        {
            mp[arr[i]]--;
            K--;
  
            if (K == 0)
            {
                i++;
                  
                while (i < N) 
                {
                    V.Add(arr[i]);
                    i++;
                }
            }
  
            if (V.Count > 0)
            {
                P.Add(new List<int>(V));
                V.Clear();
            }
        }
    }
  
    // Print the ans
    Console.WriteLine(ans);
      
    // Print the partition
    foreach (List<int> subList in P)
    {
        foreach (int item in subList)
        {
            Console.Write(item+" ");
        }
        Console.WriteLine();
    }
}
  
// Driver code
public static void Main()
{
      
    // Input
    int []A = { 5, 3, 2, 7, 6, 4 };
    int N = A.Length;
    int K = 3;
  
    // Function call
    partitionIntoKSegments(A, N, K);
}
}
  
// This code is contributed by SURENDRA_GANGWAR

<script>
// Javascript program for tha above approach
  
// Function to split the array into K
// subarrays such that the sum of
// maximum of each subarray is maximized
function partitionIntoKSegments(arr, N, K) 
{
  
    // If N is less than K
    if (N < K) {
        document.write(-1 + "<br>");
        return;
    }
      
    // Map to store the K
    // largest elements
    let mp = new Map();
  
    // Auxiliary array to
    // store and sort arr[]
    let temp = new Array(N);
  
    // Stores the maximum sum
    let ans = 0;
  
    // Copy arr[] to temp[]
    for (let i = 0; i < N; i++) {
        temp[i] = arr[i];
    }
  
    // Sort array temp[] in
    // descending order
    temp.sort((a, b) => a - b).reverse();
  
    // Iterate in the range [0, K - 1]
    for (let i = 0; i < K; i++) {
  
        // Increment sum by temp[i]
        ans += temp[i];
  
        // Increment count of
        // temp[i] in the map mp
        if (mp.has(temp[i])) {
            mp.set(temp[i], mp.get(temp[i]) + 1)
        } else {
            mp.set(temp[i], 1)
        }
    }
  
    // Stores the partitions
    let P = [];
  
    // Stores temporary subarrays
    let V = [];
  
    // Iterate over the range [0, N - 1]
    for (let i = 0; i < N; i++) {
        V.push(arr[i]);
  
        // If current element is
        // one of the K largest
        if (mp.get(arr[i]) > 0) 
        {
  
            mp.set(arr[i], mp.get(arr[i]) - 1)
            K--;
  
            if (K == 0) {
                i++;
                while (i < N) {
                    V.push(arr[i]);
                    i++;
                }
            }
  
            if (V.length) {
                P.push(V);
                V = [];
            }
        }
    }
  
    // Print the ans
    document.write(ans + "<br>");
  
    // Print the partition
    for (let u of P) {
        for (let x of u)
            document.write(x + " ");
        document.write("<br>");
    }
}
  
// Driver code
// Input
let A = [5, 3, 2, 7, 6, 4];
let N = A.length
let K = 3;
  
// Function call
partitionIntoKSegments(A, N, K);
  
// This code is contributed by sanjoy_62.
</script>

18
5 
3 2 7 
6 4

Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array