Split array into subarrays such that sum of difference between their maximums and minimums is maximum | C ++ program for the above approach ; Function to find maximum sum of difference between maximums and minimums in the splitted subarrays ; Base Case ; Traverse the array ; Stores the maximum and minimum elements upto the i - th index ; Traverse the range [ 0 , i ] ; Update the minimum ; Update the maximum ; Update dp [ i ] ; Return the maximum sum of difference ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getValue ( int arr [ ] , int N ) { int dp [ N ] ; memset ( dp , 0 , sizeof ( dp ) ) ; dp [ 0 ] = 0 ; for ( int i = 1 ; i < N ; i ++ ) { int minn = arr [ i ] ; int maxx = arr [ i ] ; for ( int j = i ; j >= 0 ; j -- ) { minn = min ( arr [ j ] , minn ) ; maxx = max ( arr [ j ] , maxx ) ; dp [ i ] = max ( dp [ i ] , maxx - minn + ( ( j >= 1 ) ? dp [ j - 1 ] : 0 ) ) ; } } return dp [ N - 1 ] ; } int main ( ) { int arr [ ] = { 8 , 1 , 7 , 9 , 2 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << getValue ( arr , N ) ; return 0 ; }