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
Yes.
Assume that
we can partition $$$[l, r]$$$ into ($$$[l, m]$$$ and $$$[m + 1, r]$$$) or ($$$[l, m - 1]$$$ and $$$[m, r]$$$) only depend on $$$2 a_{m} - a_{m - 1} - a_{m + 1}$$$, and the best one is the answer. The general case is similar.
Much harder version appeared on COCI this year.
just want to ask is there any copyright on this problem, because hackerearth used same problem, hackerearth copies problems shamelessly.
What is the name of the task and what round is it?
Contest #5 problem Sjeckanje
Another way you can think of maximizing the sum of (max-min) is to relax it into the problem where from each subsequence you can select any element as the ‘positive’ one and any other element (potentially the same one) as the ‘negative’ element, and maximize the resulting sum.
Then you can solve the relaxed problem by computing $$$dp(i, 0/1/2)$$$ meaning the best answer on $$$A[1..i]$$$ where you have selected [no element/‘negative’ element/‘positive’ element] from the current subsequence. Transitions should be straightforward.