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 maximizedvoid 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 codeint 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 approachimport java.util.*;public class GFG{// Function to split the array into K// subarrays such that the sum of// maximum of each subarray is maximizedstatic 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 codepublic 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 maximizeddef 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 codeif __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 approachusing 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 maximizedstatic 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 codepublic 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 maximizedfunction 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// Inputlet A = [5, 3, 2, 7, 6, 4];let N = A.lengthlet K = 3;// Function callpartitionIntoKSegments(A, N, K);// This code is contributed by sanjoy_62.</script> |
Output:
18 5 3 2 7 6 4
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Related Topic: Subarrays, Subsequences, and Subsets in Array
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
