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

Revision en1, by yamih23436, 2021-03-15 10:13:11

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

Tags array, #partitions, #efficient solution

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English yamih23436 2021-03-15 10:13:11 615 Initial revision (published)