Split given arrays into subarrays to maximize the sum of maximum and minimum in each subarrays

0 0 5 minutes read

Given an array arr[] consisting of N integers, the task is to maximize the sum of the difference of the maximum and minimum in each subarrays by splitting the given array into non-overlapping subarrays.

Examples:

Input: arr[] = {8, 1, 7, 9, 2}
Output: 14
Explanation:
Split the given array arr[] as {8, 1}, {7, 9, 2}. Now, the sum of the difference maximum and minimum for all the subarrays is (8 – 7) + (9 – 2) = 7 + 7 = 14, which is maximum among all possible combinations.

Input: arr[] = {1, 2, 1, 0, 5}
Output: 6

Approach: The given problem can be solved by considering all possible breaking of subarrays and find the sum of the difference of the maximum and minimum in each subarray and maximize this value. This idea can be implemented using Dynamic Programming. Follow the steps below to solve the given problem:

Initialize an array, dp[] with all elements as 0 such that dp[i] stores the sum of all possible splitting of the first i elements such that the sum of the difference of the maximum and minimum in each subarray is maximum.
Traverse the given array arr[] using the variable i and perform the following steps:
- Choose the current value as the maximum and the minimum element for the subarrays and store it in variables, say minValue and maxValue respectively.
- Iterate a loop over the range [0, i] using the variable j and perform the following steps:
  - Update the minValue and maxValue with the array element arr[j].
  - If the value of j is positive then update dp[i] as the maximum of dp[i] and (maxValue – minValue + dp[j – 1]). Otherwise, update dp[i] as the maximum of dp[i] and (maxValue – minValue).
After completing the above steps, print the value of dp[N – 1] as the resultant maximum value.

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 the maximum sum of
// differences of subarrays by splitting
// array into non-overlapping subarrays
int maxDiffSum(int arr[], int n)
{
    // Stores the answer for prefix
    // and initialize with zero
    int dp[n];
    memset(dp, 0, sizeof(dp));
 
    // Assume i-th index as right endpoint
    for (int i = 0; i < n; i++) {
 
        // Choose the current value as
        // the maximum and minimum
        int maxVal = arr[i], minVal = arr[i];
 
        // Find the left endpoint and
        // update the array dp[]
        for (int j = i; j >= 0; j--) {
            minVal = min(minVal, arr[j]);
            maxVal = max(maxVal, arr[j]);
 
            if (j - 1 >= 0)
                dp[i] = max(
                    dp[i], maxVal - minVal + dp[j - 1]);
            else
                dp[i] = max(
                    dp[i], maxVal - minVal);
        }
    }
 
    // Return answer
    return dp[n - 1];
}
 
// Driver Code
int main()
{
    int arr[] = { 8, 1, 7, 9, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << maxDiffSum(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
class GFG {
 
    // Function to find the maximum sum of
    // differences of subarrays by splitting
    // array into non-overlapping subarrays
    static int maxDiffSum(int[] arr, int n)
    {
       
        // Stores the answer for prefix
        // and initialize with zero
        int[] dp = new int[n];
 
        // Assume i-th index as right endpoint
        for (int i = 0; i < n; i++) {
 
            // Choose the current value as
            // the maximum and minimum
            int maxVal = arr[i], minVal = arr[i];
 
            // Find the left endpoint and
            // update the array dp[]
            for (int j = i; j >= 0; j--) {
                minVal = Math.min(minVal, arr[j]);
                maxVal = Math.max(maxVal, arr[j]);
 
                if (j - 1 >= 0)
                    dp[i] = Math.max(
                        dp[i], maxVal - minVal + dp[j - 1]);
                else
                    dp[i]
                        = Math.max(dp[i], maxVal - minVal);
            }
        }
 
        // Return answer
        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.print(maxDiffSum(arr, N));
    }
}
 
// This code is contributed by shivanisinghss2110

Python3

# Python Program to implement
# the above approach
 
# Function to find the maximum sum of
# differences of subarrays by splitting
# array into non-overlapping subarrays
def maxDiffSum(arr, n):
 
    # Stores the answer for prefix
    # and initialize with zero
    dp = [0] * n
 
    # Assume i-th index as right endpoint
    for i in range(n):
 
        # Choose the current value as
        # the maximum and minimum
        maxVal = arr[i]
        minVal = arr[i]
 
        # Find the left endpoint and
        # update the array dp[]
        for j in range(i, -1, -1):
            minVal = min(minVal, arr[j])
            maxVal = max(maxVal, arr[j])
 
            if (j - 1 >= 0):
                dp[i] = max(
                    dp[i], maxVal - minVal + dp[j - 1])
            else:
                dp[i] = max(
                    dp[i], maxVal - minVal)
 
    # Return answer
    return dp[n - 1]
 
# Driver Code
arr = [8, 1, 7, 9, 2]
N = len(arr)
 
print(maxDiffSum(arr, N))
 
# This code is contributed by _saurabh_jaiswal

C#

// C# program for the above approach
using System;
class GFG {
 
    // Function to find the maximum sum of
    // differences of subarrays by splitting
    // array into non-overlapping subarrays
    static int maxDiffSum(int[] arr, int n)
    {
       
        // Stores the answer for prefix
        // and initialize with zero
        int[] dp = new int[n];
 
        // Assume i-th index as right endpoint
        for (int i = 0; i < n; i++) {
 
            // Choose the current value as
            // the maximum and minimum
            int maxVal = arr[i], minVal = arr[i];
 
            // Find the left endpoint and
            // update the array dp[]
            for (int j = i; j >= 0; j--) {
                minVal = Math.Min(minVal, arr[j]);
                maxVal = Math.Max(maxVal, arr[j]);
 
                if (j - 1 >= 0)
                    dp[i] = Math.Max(
                        dp[i], maxVal - minVal + dp[j - 1]);
                else
                    dp[i]
                        = Math.Max(dp[i], maxVal - minVal);
            }
        }
 
        // Return answer
        return dp[n - 1];
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = { 8, 1, 7, 9, 2 };
        int N = arr.Length;
 
        Console.WriteLine(maxDiffSum(arr, N));
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
       // JavaScript Program to implement
       // the above approach
 
       // Function to find the maximum sum of
       // differences of subarrays by splitting
       // array into non-overlapping subarrays
       function maxDiffSum(arr, n) 
       {
        
           // Stores the answer for prefix
           // and initialize with zero
           let dp = new Array(n).fill(0);
 
           // Assume i-th index as right endpoint
           for (let i = 0; i < n; i++) {
 
               // Choose the current value as
               // the maximum and minimum
               let maxVal = arr[i], minVal = arr[i];
 
               // Find the left endpoint and
               // update the array dp[]
               for (let j = i; j >= 0; j--) {
                   minVal = Math.min(minVal, arr[j]);
                   maxVal = Math.max(maxVal, arr[j]);
 
                   if (j - 1 >= 0)
                       dp[i] = Math.max(
                           dp[i], maxVal - minVal + dp[j - 1]);
                   else
                       dp[i] = Math.max(
                           dp[i], maxVal - minVal);
               }
           }
 
           // Return answer
           return dp[n - 1];
       }
 
       // Driver Code
       let arr = [8, 1, 7, 9, 2];
       let N = arr.length;
 
       document.write(maxDiffSum(arr, N));
 
    // This code is contributed by Potta Lokesh
   </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!