Split given arrays into subarrays to maximize the sum of maximum and minimum in each subarrays | 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
def maxDiffSum ( arr , n ) : NEW_LINE INDENT dp = [ 0 ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT maxVal = arr [ i ] NEW_LINE minVal = arr [ i ] NEW_LINE for j in range ( i , - 1 , - 1 ) : NEW_LINE INDENT minVal = min ( minVal , arr [ j ] ) NEW_LINE maxVal = max ( maxVal , arr [ j ] ) NEW_LINE if ( j - 1 >= 0 ) : NEW_LINE INDENT dp [ i ] = max ( dp [ i ] , maxVal - minVal + dp [ j - 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] = max ( dp [ i ] , maxVal - minVal ) NEW_LINE DEDENT DEDENT DEDENT return dp [ n - 1 ] NEW_LINE DEDENT arr = [ 8 , 1 , 7 , 9 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE print ( maxDiffSum ( arr , N ) ) NEW_LINE