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

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.

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

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).