I know the O(n*n) partitional dp solution for this problem . Looking for a more efficient one . This problem was asked in a coding test of Hacker|earth 10 days back .

How to maximize the total sum of difference of maximum and minimum element in contiguous subarrays of an array ?

We can partition an array into any number of subarrays we want. Each element should belong to exactly one subarray .

$$$A=[3,1,7,8] $$$

$$$Ans=[3],[1,7,8]$$$

$$$Ans= (3-3)+(8-1)=7$$$

If $$$A=[3,1,6,5,9,2]$$$

$$$Subarrays:[3],[1,6,5],[9,2]$$$

$$$Ans= 12$$$

(3-3)+(6-1)+(9-2)=12