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 approachÂ
import 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!
