I didn't understand the editorial as well, so I came up with this solution: Firstly the sum in the statement is equal to the sum of differences between all pairs in the whole array — (sum of differences between all pairs in Li's set + sum of differences between all pairs in Lu's set). So this way you want to find the maximum value of the sum of the differences between all pairs in the two independent sets. Suppose the set is sorted. Then how do you find this sum ? Let's say that the set size is T. Then the element with index I in the sorted set will be added exactly I — 1 — (T — I) = 2 * I — T — 1 times. So this way we can reduce our task to: You have one array of size K with the coefficients shown above and another one of size N-K. Put numbers in the both sets in such way that it's sorted and the sum of them multiplied by the corresponding coefficients is maximum possible. This leads us to a straightforward DP with states 1) position in the first array. 2) positions in the second array. Now how do you do the transitions ? Firstly sort the whole array. Now it's pretty obvious that DP[i][j] = max(DP[i-1][j] + c1[i] * arr[i+j], DP[i][j-1] + c2[j] * arr[i+j]), where c1 and c2 are the arrays with the coefficients. You don't need the position in the big array as a state, because you know it — it's the sum of the position in the first array + position in the second array. Now the answer is the sum of differences between all pairs in the whole array — DP[K][N-K]. I can give you an accepted code if something is not clear or you doubt about the solution / implementation.