Maximizing difference in partitioned Subarrays
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 code int 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); } } |
Python
# Function to calculate the maximum sum after partitioning the array def maxSumAfterPartitioning(arr, k): n = len (arr) dp = [ 0 ] * (n + 1 ) # Loop through the array in reverse for s in range (n - 1 , - 1 , - 1 ): curr_sum = float ( '-inf' ) # Initialize current sum max_ele = float ( '-inf' ) # Initialize maximum element # Loop through the next k elements or until the end of the array for i in range (s, min (s + k, n)): max_ele = max (max_ele, arr[i]) # Update maximum element curr_sum = max (curr_sum, dp[i + 1 ] + max_ele * (i - s + 1 )) # Update current sum dp[s] = curr_sum # Update the dp vector return dp[ 0 ] # Return the maximum sum # Function to calculate the minimum sum after partitioning the array def minSumAfterPartitioning(arr, k): n = len (arr) dp = [ 0 ] * (n + 1 ) # Loop through the array in reverse for s in range (n - 1 , - 1 , - 1 ): curr_sum = float ( 'inf' ) # Initialize current sum min_ele = float ( 'inf' ) # Initialize minimum element # Loop through the next k elements or until the end of the array for i in range (s, min (s + k, n)): min_ele = min (min_ele, arr[i]) # Update minimum element curr_sum = min (curr_sum, dp[i + 1 ] + min_ele * (i - s + 1 )) # Update current sum dp[s] = curr_sum # Update the dp vector return dp[ 0 ] # Return the minimum sum # Driver code arr = [ 3 , 7 , 2 , 2 , 6 ] k = 2 # Print the difference between max and min sums print (maxSumAfterPartitioning(arr, k) - minSumAfterPartitioning(arr, k)) |
C#
using System; 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 = int .MinValue; int maxElement = int .MinValue; // 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 array 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 = int .MaxValue; int minElement = int .MaxValue; // 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 array 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; Console.WriteLine(difference); } } |
Javascript
// Javascript code for the above approach function maxSumAfterPartitioning(arr, k) { // Get the size of the array let n = arr.length; // Initialize a dp array of size n+1 to // prevent access to unallocated memory // while updating the curr_sum let dp = new Array(n + 1).fill(0); // Loop through the array in reverse for (let s = n - 1; s >= 0; s--) { // Initialize current sum and maximum // element with very small values let curr_sum = Number.MIN_SAFE_INTEGER; let max_ele = Number.MIN_SAFE_INTEGER; // Loop through the next k elements or // until the end of the array for (let i = s; i < Math.min(s + k, n); i++) { // Update maximum element max_ele = Math.max(max_ele, arr[i]); // Update current sum curr_sum = Math.max(curr_sum, dp[i + 1] + max_ele * (i - s + 1)); } // Update the dp array dp[s] = curr_sum; } // Return the maximum sum return dp[0]; } function minSumAfterPartitioning(arr, k) { // Get the size of the array let n = arr.length; // Initialize a dp array of size n+1 to // prevent access to unallocated memory // while updating the curr_sum let dp = new Array(n + 1).fill(0); // Loop through the array in reverse for (let s = arr.length - 1; s >= 0; s--) { // Initialize current sum and minimum // element with very large values let curr_sum = Number.MAX_SAFE_INTEGER; let min_ele = Number.MAX_SAFE_INTEGER; // Loop through the next k elements or // until the end of the array for (let i = s; i < Math.min(s + k, n); i++) { // Update minimum element min_ele = Math.min(min_ele, arr[i]); // Update current sum curr_sum = Math.min(curr_sum, dp[i + 1] + min_ele * (i - s + 1)); } // Update the dp array dp[s] = curr_sum; } // Return the minimum sum return dp[0]; } // Drivers code let arr = [3, 7, 2, 2, 6]; let k = 2; // Print the difference between // max and min sums console.log(maxSumAfterPartitioning(arr, k) - minSumAfterPartitioning(arr, k)); |
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.
Contact Us