Split given arrays into subarrays to maximize the sum of maximum and minimum in each subarrays | C ++ program for the above approach ; Function to find the maximum sum of differences of subarrays by splitting array into non - overlapping subarrays ; Stores the answer for prefix and initialize with zero ; Assume i - th index as right endpoint ; Choose the current value as the maximum and minimum ; Find the left endpoint and update the array dp [ ] ; Return answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxDiffSum ( int arr [ ] , int n ) { int dp [ n ] ; memset ( dp , 0 , sizeof ( dp ) ) ; for ( int i = 0 ; i < n ; i ++ ) { int maxVal = arr [ i ] , minVal = arr [ i ] ; 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 dp [ n - 1 ] ; } int main ( ) { int arr [ ] = { 8 , 1 , 7 , 9 , 2 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maxDiffSum ( arr , N ) ; return 0 ; }