Split array into subarrays such that sum of difference between their maximums and minimums is maximum | Java 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
import java . util . * ; public class Main { static int getValue ( int [ ] arr , int N ) { int dp [ ] = new int [ N ] ; dp [ 0 ] = 0 ; for ( int i = 1 ; i < N ; i ++ ) { int min = arr [ i ] ; int max = arr [ i ] ; for ( int j = i ; j >= 0 ; j -- ) { min = Math . min ( arr [ j ] , min ) ; max = Math . max ( arr [ j ] , max ) ; dp [ i ] = Math . max ( dp [ i ] , max - min + ( ( j >= 1 ) ? dp [ j - 1 ] : 0 ) ) ; } } return dp [ N - 1 ] ; } public static void main ( String args [ ] ) { int arr [ ] = { 8 , 1 , 7 , 9 , 2 } ; int N = arr . length ; System . out . println ( getValue ( arr , N ) ) ; } }