yamih23436's blog

Can this array problem be solved in O(N) time ?

By yamih23436, history, 4 years ago, In English

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

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Much harder version appeared on COCI this year.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -39 Vote: I do not like it

    just want to ask is there any copyright on this problem, because hackerearth used same problem, hackerearth copies problems shamelessly.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    What is the name of the task and what round is it?

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +66 Vote: I do not like it

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.

→ Reply