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