Given an array arr[] consisting of N integers, the task is to split the array into subarrays such that the sum of the difference between the maximum and minimum elements for all the subarrays is maximum.
Examples :
Input: arr[] = {8, 1, 7, 9, 2}
Output: 14
Explanation:
Consider splitting the given array into subarrays as {8, 1} and {7, 9, 2}. Now, the difference between maximum and minimum elements are:
- {8, 1}: Difference is (8 – 1) = 7.
- {7, 9, 2}: Difference is (9 – 2) = 7.
Therefore, the sum of the difference is 7 + 7 = 14.
Input: arr[] = {1, 2, 1, 0, 5}
Output: 6
Approach: The given problem can be solved by using Dynamic Programming. Follow the steps to solve the problem:
- Initialize an array, say dp[], where dp[i] represents the maximum sum of the difference between the maximum and minimum element for all the subarray for the first i array element.
- Initialize dp[0] as 0.
- Traverse the given array over the range [1, N – 1] and perform the following steps:
- Initialize a variable, say min as arr[i], that stores the minimum element over the range [0, i].
- Initialize a variable, say max as arr[i], that stores the maximum element over the range [0, i].
- Iterate over the range [0, i] using the variable j in the reverse order and perform the following steps:
- Update the value of min as the minimum of min and arr[j].
- Update the value of max as the minimum of max and arr[j].
- Update the value of dp[j] to the maximum of dp[j] and (max – min + dp[i]).
- After completing the above steps, print the value of dp[N – 1] as the result.
Below is the implementation of the above approach :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum sum of// difference between maximums and// minimums in the splitted subarraysint getValue(int arr[], int N){ int dp[N]; memset(dp, 0, sizeof(dp)); // Base Case dp[0] = 0; // Traverse the array for(int i = 1; i < N; i++) { // Stores the maximum and // minimum elements upto // the i-th index int minn = arr[i]; int maxx = arr[i]; // Traverse the range [0, i] for(int j = i; j >= 0; j--) { // Update the minimum minn = min(arr[j], minn); // Update the maximum maxx = max(arr[j], maxx); // Update dp[i] dp[i] = max(dp[i], maxx - minn + ((j >= 1) ? dp[j - 1] : 0)); } } // Return the maximum // sum of difference return dp[N - 1];}// Driver codeint main(){ int arr[] = { 8, 1, 7, 9, 2 }; int N = sizeof(arr) / sizeof(arr[0]); cout << getValue(arr, N); return 0;}// This code is contributed by Kingash |
Java
// Java program for the above approachimport java.util.*;public class Main { // Function to find maximum sum of // difference between maximums and // minimums in the splitted subarrays static int getValue(int[] arr, int N) { int dp[] = new int[N]; // Base Case dp[0] = 0; // Traverse the array for (int i = 1; i < N; i++) { // Stores the maximum and // minimum elements upto // the i-th index int min = arr[i]; int max = arr[i]; // Traverse the range [0, i] for (int j = i; j >= 0; j--) { // Update the minimum min = Math.min(arr[j], min); // Update the maximum max = Math.max(arr[j], max); // Update dp[i] dp[i] = Math.max( dp[i], max - min + ((j >= 1) ? dp[j - 1] : 0)); } } // Return the maximum // sum of difference return dp[N - 1]; } // Driver Code public static void main(String args[]) { int arr[] = { 8, 1, 7, 9, 2 }; int N = arr.length; System.out.println(getValue(arr, N)); }} |
C#
// C# program for the above approachusing System;class GFG{// Function to find maximum sum of// difference between maximums and// minimums in the splitted subarraysstatic int getValue(int[] arr, int N){ int[] dp = new int[N]; // Base Case dp[0] = 0; // Traverse the array for(int i = 1; i < N; i++) { // Stores the maximum and // minimum elements upto // the i-th index int min = arr[i]; int max = arr[i]; // Traverse the range [0, i] for(int j = i; j >= 0; j--) { // Update the minimum min = Math.Min(arr[j], min); // Update the maximum max = Math.Max(arr[j], max); // Update dp[i] dp[i] = Math.Max( dp[i], max - min + ((j >= 1) ? dp[j - 1] : 0)); } } // Return the maximum // sum of difference return dp[N - 1];}// Driver Codestatic public void Main(){ int[] arr = { 8, 1, 7, 9, 2 }; int N = arr.Length; Console.Write(getValue(arr, N));}}// This code is contributed by code_hunt |
Python3
# python 3 program for the above approach# Function to find maximum sum of# difference between maximums and# minimums in the splitted subarraysdef getValue(arr, N): dp = [0 for i in range(N)] # Traverse the array for i in range(1, N): # Stores the maximum and # minimum elements upto # the i-th index minn = arr[i] maxx = arr[i] j = i # Traverse the range [0, i] while(j >= 0): # Update the minimum minn = min(arr[j], minn) # Update the maximum maxx = max(arr[j], maxx) # Update dp[i] dp[i] = max(dp[i], maxx - minn + (dp[j - 1] if (j >= 1) else 0)) j -= 1 # Return the maximum # sum of difference return dp[N - 1]# Driver codeif __name__ == '__main__': arr = [8, 1, 7, 9, 2] N = len(arr) print(getValue(arr, N)) # This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script>// JavaScript program to implement// the above approach // Function to find maximum sum of // difference between maximums and // minimums in the splitted subarrays function getValue(arr, N) { let dp = Array.from({length: N}, (_, i) => 0); // Base Case dp[0] = 0; // Traverse the array for (let i = 1; i < N; i++) { // Stores the maximum and // minimum elements upto // the i-th index let min = arr[i]; let max = arr[i]; // Traverse the range [0, i] for (let j = i; j >= 0; j--) { // Update the minimum min = Math.min(arr[j], min); // Update the maximum max = Math.max(arr[j], max); // Update dp[i] dp[i] = Math.max( dp[i], max - min + ((j >= 1) ? dp[j - 1] : 0)); } } // Return the maximum // sum of difference return dp[N - 1]; }// Driver code let arr = [ 8, 1, 7, 9, 2 ]; let N = arr.length; document.write(getValue(arr, N)); </script> |
Output:
14
Time Complexity: O(N2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!