The problem of maximising the sum of the max and min of each of the K subarrays obtained by dividing a given array into given sizes is a widely asked interview question. It has a wide range of applications in various fields. Such as portfolio optimisation, task scheduling etc., thus making it a valuable tool for solving practical problems.
This problem checks the aptitude and problem-solving skills of the candidate. Let’s dive further into this question and talk about its problem statement.
Problem Statement
You are given two arrays. The first array is called ‘num’ of size ‘n’ and the ‘divisors’ of size ‘m’. We have to divide the array ‘num’ into ‘m’ subarrays. Note that these subarrays need not have continuous elements. Our task is to do it in such a way that the summation of the maximum and minimum values of each subarray is maximum. The size of these subarrays are elements of the array ‘divisors’.
Have a look at the below example to better understand the problem statement.
Example
Example 1:
Consider n = 5 and m = 2.
Num = {5, 7, 6, 1, 4}
Divisor = {2, 3}
Explanation:
The MaxSum of this example will be 19. We are given n = 5 and m = 2. We have to divide our array num into two subarrays (because m=2). The size of these subarrays will be {2, 3}. It is because we are given the size in which we are supposed to break our subarray as elements of the divisor. See the above diagram. The optimal way to partition the array is:
First, sort the array “num” in descending order.
Now we will now put the first and second elements of the “num” as the first element of subarrays 1 and 2.
We will then put the rest elements in pairs afterwards, thus arranging the elements of the array.
Let’s see another example to better understand how we put elements in the subarrays.
Example 2:
Consider n = 8 and m = 4.
Num = {5, 7, 6, 1, 4, 8, 3, 2}
Divisor = {1, 1, 3, 3}
Explanation:
The MaxSum of this example will be 45. We divided the array as we did in the previous example. The optimal way to partition the array is:
First, sort the array “num” in descending order.
Now, put the first four elements of the “num” as the first element of subarrays 1, 2. 3 and 4.
Now, put the rest elements in pairs {4, 3} and {2, 1} afterwards, thus arranging the elements of the array.
Approach
The approach used for this problem can be described as a "greedy algorithm" approach. With the help of the greedy algorithm, we select the current maximum and minimum elements in each divided array. It helps us to maximise the total sum of all the divided arrays. This approach is often used in optimisation problems where finding the optimal solution is difficult, but finding a good solution quickly is still valuable.
Now let’s discuss the algorithm for this problem.
Algorithm
Define a function "calculateMaxSum" that takes in two vectors, "num" and "divisors", by reference and returns an integer.
Get the size of both vectors "num" and "divisors".
Sort "num" in descending order.
Sort "divisors" in ascending order.
Sorting the 'nums' array in descending order and the 'divisors' array in ascending order ensures that the larger elements of the num arrays are distributed to the smaller arrays first. This maximises the sum of maximum and minimum elements for each subarray.
Count how many 1-size subarrays are to be made.
Declare a variable "maxSum" and initialise it to zero.
Iterate over the first "m" largest numbers in "num" and add a maximum term in the answer. If there are 1-size subarrays, add the term "num[i]" to "maxSum" again, as for one-sized arrays, both the max and min elements are the same.
After the previous step, we added the max elements to each of the subarrays. Now, to add the minimum terms to each of the subarrays, start from the "m"th element of the "num".
Find the following minimum element index to be added and add it to "maxSum".
Return "maxSum" as the answer.
Now, coming to the main function:
First, initialise the vector "num" and "divisors" with the input values.
Afterwards, call the function "calculateMaxSum" with the "num" and "divisors" and store the result in "maxSum".
At last, print the "maxSum".
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
// Function to maximize the sum of max and min of K subarrays.
int calculateMaxSum(vector < int > & nums, vector < int > & divisors) {
// Get the size of both vectors.
int n = nums.size();
int m = divisors.size();
// Sort 'nums' in descending order.
sort(nums.begin(), nums.end(), greater < int > ());
// Sort 'divisors' in ascending order.
sort(divisors.begin(), divisors.end());
// Number of 1-size subarrays.
int numberOfOnes = 0;
// Count how many numbers of 1-size subarrays are to be made.
for (int i = 0; i < m; i++) {
if (divisors[i] == 1) {
numberOfOnes++;
}
}
// Store the count in 'tempCount'.
int tempCount = numberOfOnes;
// Declare and initialise 'maxSum'.
int maxSum = 0;
// Now iterate over the first 'm' greater numbers in 'nums' and add a maximum term in the answer.
for (int i = 0; i < m; i++) {
maxSum += nums[i];
// If there are 1 size subarrays add the 'nums[i]' value to 'maxSum'.
if (numberOfOnes > 0) {
numberOfOnes--;
maxSum += nums[i];
}
}
// Now, to add the minimum terms of the subarray, start from the 'm'th element in 'nums.'
for (int i = m; i < n; i++) {
// Find the following minimum element index to be added.
i += divisors[tempCount] - 2;
// Add the minimum element to 'maxSum'.
maxSum += nums[i];
tempCount++;
}
// Return 'maxSum'.
return maxSum;
}
int main() {
vector < int > nums = {
5,
10,
15,
20,
25,
30,
35,
40,
45,
50
};
vector < int > divisors = {
1,
2,
3,
4
};
// Calling function 'calculateMaxSum()'.
int maxSum = calculateMaxSum(nums, divisors);
cout << "Maximum sum is: " << maxSum << endl;
return 0;
}
You can also try this code with Online C++ Compiler
#Function to maximize the sum of max and min of K subarrays.
def calculateMaxSum(num, divisor, n, m):
# Variable to numberOfOnes in divisor[]
numberOfOnes = 0
for i in range(m):
if (divisor[i] == 1):
numberOfOnes += 1
# Sort num[] in descending order
num.sort()
num.reverse()
# Sort divisor[] in ascending order
divisor.sort()
# Temporary variable to store
tempCount = numberOfOnes
# Initialise 'maxSum'
maxSum = 0
# Now iterate over the first 'm' greater numbers in 'nums' and add a maximum term in the answer
for i in range(m):
maxSum += num[i]
if (numberOfOnes > 0):
numberOfOnes -= 1
maxSum += num[i]
# Now, to add the minimum terms of the subarray, start from the 'm'th element in 'nums'
i = m
while(i < n):
# Update the index
i += divisor[tempCount] - 2
# Add the minimum element to 'maxSum'
maxSum += num[i]
tempCount += 1
i += 1
# Return 'maxSum'.
return maxSum
num = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
divisor = [1, 2, 3, 4]
n = len(num)
m = len(divisor)
# Calling function 'calculateMaxSum()'
print("Maximum sum is:", calculateMaxSum(num, divisor, n, m))
You can also try this code with Online Python Compiler
In the above program, we had done three things. First, we sorted the 'nums' vector in descending order and the 'divisors' vector in ascending order. We did this to ensure that the largest and smallest elements were selected first. It ensures that the divisors are used in increasing order.
Afterwards, we counted the number of 1-size subarrays that needed to be made. For this, we iterated over the 'divisors' vector and counted how many elements were equal to 1.
Now, the 'maxSum' variable is then initialised to 0. First, sort the array “num” in descending order. Now we will now put the first and second elements of the “num” as the first element of subarrays 1 and 2. We will then put the rest elements in pairs afterwards, thus arranging the elements of the array. See the below diagram.
Time Complexity
The time complexity of the algorithm used above is O(N*logN). Here, N is the size of the input array. The sorting step at the beginning of the algorithm causes the time complexity to become O(N*logN).
Space Complexity
The space complexity of the above algorithm is O(1). It is because the algorithm uses only a few constant-size variables to compute the final result.
Frequently Asked Questions
What is a greedy algorithm?
A greedy algorithm solves optimisation problems by making locally optimal choices at each step to find a global optimum. The algorithm makes the best possible decision at each stage of the problem without considering the consequences of that decision in the future.
What is call by reference?
Call by reference is a method of passing arguments to a function where the memory address of the variable is passed instead of the value itself. This means any changes made to the variable within the function also affect the original variable outside the function.
Which is the most optimised sorting algorithm?
An optimised sorting algorithm depends on the requirements of the problem. For example, for small arrays, insertion sort is the fastest. For larger arrays, merge sort and quicksort are commonly used, with quicksort being faster in most cases. A modified insertion sort, shell sort, is used for partially sorted data.
Conclusion
This article briefly discussed the problem of maximising the sum of the max and min of each of the K subarrays obtained by dividing a given array into given sizes. We used a greedy approach to solve this problem.
For further reading, refer to our articles on similar topics: