Split array into subarrays such that sum of difference between their maximums and minimums is maximum

0 0 5 minutes read

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 subarrays
int 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 code
int 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 approach
using System;
 
class GFG{
 
// 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
static 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 subarrays
def 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 code
if __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:

Time Complexity: O(N²)
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 zambiatek!