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 ; 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
def getValue ( arr , N ) : NEW_LINE INDENT dp = [ 0 for i in range ( N ) ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT minn = arr [ i ] NEW_LINE maxx = arr [ i ] NEW_LINE j = i NEW_LINE while ( j >= 0 ) : NEW_LINE INDENT minn = min ( arr [ j ] , minn ) NEW_LINE maxx = max ( arr [ j ] , maxx ) NEW_LINE dp [ i ] = max ( dp [ i ] , maxx - minn + ( dp [ j - 1 ] if ( j >= 1 ) else 0 ) ) NEW_LINE j -= 1 NEW_LINE DEDENT DEDENT return dp [ N - 1 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 8 , 1 , 7 , 9 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE print ( getValue ( arr , N ) ) NEW_LINE DEDENT