Блог пользователя yamih23436

Автор yamih23436, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

Yes.

Assume that

$$$ a_l \leq a_{l + 1} \leq \cdots \leq a_{m - 1} \leq a_{m} \geq a_{m + 1} \geq \cdots \geq a_{r} $$$

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.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Much harder version appeared on COCI this year.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +66 Проголосовать: не нравится

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.