Split array into subarrays such that sum of difference between their maximums and minimums is maximum | 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
function getValue ( arr , N ) { let dp = Array . from ( { length : N } , ( _ , i ) => 0 ) ; dp [ 0 ] = 0 ; for ( let i = 1 ; i < N ; i ++ ) { let min = arr [ i ] ; let max = arr [ i ] ; for ( let 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 ] ; } let arr = [ 8 , 1 , 7 , 9 , 2 ] ; let N = arr . length ; document . write ( getValue ( arr , N ) ) ;