Split array into K subarrays such that sum of maximum of all subarrays is maximized

0 0 8 minutes read

Given an array arr[] of size N and a number K, the task is to partition the given array into K contiguous subarrays such that the sum of the maximum of each subarray is the maximum possible. If it is possible to split the array in such a manner, then print the maximum possible sum. Otherwise, print “-1“.

Examples:

Input: arr[] = {5, 3, 2, 7, 6, 4}, N = 6, K = 3
Output: 18
5
3 2 7
6 4
Explanation:
One way is to split the array at indices 0, 3 and 4.
Therefore, the subarrays formed are {5}, {3, 2, 7} and {6, 4}.
Therefore, sum of the maximum of each subarray = 5 + 7 + 6 =18 ( which is the maximum possible).

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

Approach: The given problem can be solved using Map data structure and Sorting techniques, based on the following observations:

The maximum obtainable sum would be the sum of the K-largest elements of the array as it is always possible to divide the array into K segments in such a way that the maximum of each segment is one of the K-largest elements.

One way would be to break a segment as soon as one of the K-largest element is encountered.

Follow the steps below to solve the problem:

First, if N is less than K then print “-1” and then return.
Copy array into another array say temp[] and sort the array, temp[] in descending order.
Initialize a variable ans to 0, to store the maximum sum possible.
Also, Initialize a map say mp, to store the frequency of the K-largest elements.
Iterate in the range [0, K-1] using a variable say i, and in each iteration increment the ans by temp[i] and increment the count of temp[i] in map mp.
Initialize a vector of vectors say P to store a possible partition and a vector say V to store the elements of a partition.
Iterate in the range [0, N-1] and using a variable say i and perform the following steps:
- Push the current element arr[i] in the vector V.
- If mp[arr[i]] is greater than 0 then do the following:
  - Decrement K and count of arr[i] in the map mp by 1.
  - If K is equal to 0 i.e it is the last segment then push all the remaining elements of the array arr[] in V.
  - Now push the current segment V in the P.
Finally, after completing the above steps, print the maximum sum stores in variable ans and then partition stored in P.

Below is the implementation of the above approach:

C++

// C++ program for the 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

// 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

Python3

# Python program for the 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#

// C# program for the 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

Javascript

<script>
// Javascript program for the 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>

Output:

Time Complexity: O(N*log(N))
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!