-1
$\begingroup$

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n ?

for example : for n=10 1 2 3 4 10 20 30 40 100 200

the sub-sequence of length will with minimized sum of difference will be 1 2 3 4 as |1-2| + |1-3| + |1-4| + |2-3| + |2-4| + |3-4| = 10 i.e minimum in any sequence.

$\endgroup$
  • 1
    $\begingroup$ What have you tried ? Did you get stuck somewhere ? Show us what have you done so far, then we can help you accordingly. $\endgroup$ – avi Oct 19 '13 at 10:44
  • $\begingroup$ Must the subsequence be contiguous? $\endgroup$ – Yuval Filmus Oct 21 '13 at 2:06
0
$\begingroup$

Where are the constraints? Well, since I don't know what the constraints are, I will help you with an almost naive solution. For each segment of length k (so there are n-k+1 segments) you have to order the elements, because if you have an ordered array then you can calculate that cost function of the segment as follow. For example:

array: 1 2 3 4

The cost function as you said is:

|1-2| + |1-3| + |1-4| + |2-3| + |2-4| + |3-4|

and it is equal to:

2-1 + 3-1 + 4-1 + 3-2 + 4-2 + 4-3 = 10

and it is equal to:

4*3 + 3*2 + 2*1 + 1*0 - 1*3 - 2*2 - 3*1 - 4*0 = 10

So as you can see for a general ordered array:

array: a0, a1, a2, ..., an-1 ; a0 <= a1 <= a2 <= a3.. <= an-2 <= an-1

The cost function can be calculated as:

an-1*(n-1) - an-1*(0) + an-2*(n-2) - an-2*(1)... + ak*k - ak*(n-1-k) + ... + a0*(0) - a0*(n-1)

So the time complexity for the cost function will be O(k), and the total cost will be O((n - k + 1) * (k * logk + k)) = O(n*k*logk).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.