Given array numbers[] and a value limit, the task is to partition the array into subarrays such that the size of each subarray ranges from 1 to limit, so as to obtain the maximum difference between minimum and maximum partition.
Examples:
Input: numbers = [1, 2, 3, 4, 5, 6], limit = 3
Output: 12
Explanation: Here the maximum sum after partitioning the array as [1, 2, 3] and [4, 5, 6] is 27 and the minimum sum after partitioning the array as [1, 2, 3] and [4, 5, 6] is 15, the difference obtained is 12.Input: numbers = [3, 7, 2, 2, 6], limit = 2
Output: 18
Explanation: Here the maximum sum after partitioning the array as [3], [7, 2], and [2, 6] is 29 and the minimum sum after partitioning the array as [3],[7, 2] and [2, 6] is 11, the difference obtained is 18.
Approach: To solve the problem follow the below idea:
For maximum partition:
- Get the size of the input array arr and store it in variable n.
- Create a dynamic programming vector dp of size n+1 to store the maximum sum after partitioning. At index i, dp[i] will store the maximum partition sum possible in the range [i…n]
- Iterate through the array arr in reverse order, starting from the last element.
- For each position s in the array:
- Initialize curr_sum and max_ele to very small values (INT_MIN).
- Iterate through the next k elements or until the end of the array:
- Update max_ele with the maximum value between the current element and max_ele.
- Update curr_sum with the maximum value between the current value of curr_sum and the value of dp[i + 1] plus max_ele times (i – s + 1).
- Update dp[s] with the value of curr_sum.
- Return the maximum sum stored in dp[0].
For minimum partition:
- Get the size of the input array arr and store it in variable n.
- Create a dynamic programming vector dp of size n+1 to store the minimum sum after partitioning. At an index i, dp[i] will store the minimum partition sum possible in the range [i…n]
- Iterate through the array arr in reverse order, starting from the last element.
- For each position s in the array:
- Initialize curr_sum and min_ele to very large values (INT_MAX).
- Iterate through the next k elements or until the end of the array:
- Update min_ele with the minimum value between the current element and min_ele.
- Update curr_sum with the minimum value between the current value of curr_sum and the value of dp[i + 1] plus min_ele times (i – s + 1).
- Update dp[s] with the value of curr_sum.
- Return the minimum sum stored in dp[0].
At the end Calculate the difference between the maximum and minimum sums and print it.
Below is the implementation of the above approach:
C++14
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int maxSumAfterPartitioning(vector<int>& arr, int k){ // Get the size of the array int n = arr.size(); // Initialize a dp vector of size n+1 to // prevent access to unallocated memory // while updating the curr_sum vector<int> dp(n + 1, 0); // Loop through the array in reverse for (int s = n - 1; s >= 0; s--) { // Initialize current sum and maximum // element with very small values int curr_sum = INT_MIN; int max_ele = INT_MIN; // Loop through the next k elements or // until the end of the array for (int i = s; i < min(s + k, n); i++) { // Update maximum element max_ele = max(max_ele, arr[i]); // Update current sum curr_sum = max(curr_sum, dp[i + 1] + max_ele * (i - s + 1)); } // Update the dp vector dp[s] = curr_sum; } // Return the maximum sum return dp[0];}int minSumAfterPartitioning(vector<int>& arr, int k){ // Get the size of the array int n = arr.size(); // Initialize a dp vector of size n+1 to // prevent access to unallocated memory // while updating the curr_sum vector<int> dp(n + 1, 0); // Loop through the array in reverse for (int s = arr.size() - 1; s >= 0; s--) { // Initialize current sum and minimum // element with very large values int curr_sum = INT_MAX; int min_ele = INT_MAX; // Loop through the next k elements or // until the end of the array for (int i = s; i < min(s + k, n); i++) { // Update minimum element min_ele = min(min_ele, arr[i]); // Update current sum curr_sum = min(curr_sum, dp[i + 1] + min_ele * (i - s + 1)); } // Update the dp vector dp[s] = curr_sum; } // Return the minimum sum return dp[0];}// Drivers codeint main(){ vector<int> arr = { 3, 7, 2, 2, 6 }; int k = 2; // Print the difference between // max and min sums cout << maxSumAfterPartitioning(arr, k) - minSumAfterPartitioning(arr, k); return 0;} |
Java
import java.util.Arrays;public class PartitionArrayMaxMinDifference { // Function to find the maximum sum after partitioning the array public static int maxSumAfterPartitioning(int[] arr, int k) { int n = arr.length; int[] dp = new int[n + 1]; // Loop through the array in reverse for (int s = n - 1; s >= 0; s--) { int currSum = Integer.MIN_VALUE; int maxElement = Integer.MIN_VALUE; // Loop through the next k elements or until the end of the array for (int i = s; i < Math.min(s + k, n); i++) { maxElement = Math.max(maxElement, arr[i]); currSum = Math.max(currSum, dp[i + 1] + maxElement * (i - s + 1)); } // Update the dp vector dp[s] = currSum; } // Return the maximum sum return dp[0]; } // Function to find the minimum sum after partitioning the array public static int minSumAfterPartitioning(int[] arr, int k) { int n = arr.length; int[] dp = new int[n + 1]; // Loop through the array in reverse for (int s = n - 1; s >= 0; s--) { int currSum = Integer.MAX_VALUE; int minElement = Integer.MAX_VALUE; // Loop through the next k elements or until the end of the array for (int i = s; i < Math.min(s + k, n); i++) { minElement = Math.min(minElement, arr[i]); currSum = Math.min(currSum, dp[i + 1] + minElement * (i - s + 1)); } // Update the dp vector dp[s] = currSum; } // Return the minimum sum return dp[0]; } public static void main(String[] args) { int[] arr = {3, 7, 2, 2, 6}; int k = 2; // Calculate the maximum and minimum sums after partitioning int maxSum = maxSumAfterPartitioning(arr, k); int minSum = minSumAfterPartitioning(arr, k); // Calculate and print the difference between max and min sums int difference = maxSum - minSum; System.out.println(difference); }} |
Output
18
Time Complexity: O(n*k), where “n” is the size of the input array arr, k is the limit.
Auxiliary Space: O(n) due to the dynamic programming vector dp created in both functions.
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!
