Count maximum inversions for k subarrays

Question

I have this problem:

Given an array A and an integer K, partition A into K contiguous subarrays in the way that maximizes the sum of the number of inversions in each subarray. (An "inversion" is a pair of indices i, j where i < j and A[i] > A[j].)

Return the sum.

For example, if A = 9 1 7 2 3 and K = 2, then the answer is 4, because you can split the array into 9 1 7 2 (which has four inversions) and 3 (which has none), and 4 + 0 = 4.

Constaints
1 <= A.size <= 500
1 <= k <= A.size
1 <= A[i] <= 100000

My thoughts:

This looks like a dynamic programming problem but I can't work out how to integrate K groups into the solution.
This problems roughly translates to finding K groups with each group having the highest number of increasing elements within that group.

Any ideas on how to solve this would be helpful.

can you tell a bit more why do you think this is a DP problem? I can see memoization but where is overlapping sub problems? — P.hunter
– P.hunter, Commented Dec 16, 2018 at 8:02
I don't see how you get four inversions in 1, 7, 2, 3. And don't you mean "highest number of decreasing elements"? — Nelfeal
– Nelfeal, Commented Dec 16, 2018 at 8:31
"inversions in each of the group is the maximum" is unclear. Please clarify if you are looking to maximize the total number of inversions in all groups combined or something else. — גלעד ברקן
– גלעד ברקן, Commented Dec 16, 2018 at 14:43

גלעד ברקן · Accepted Answer · 2018-12-16 18:40:46Z

2

We can at least have an O(n^2 * k) dynamic program. Let f(i, k) represent the most inversions up to index i with k groups. Then:

f(i, k) = max(
  inversion_count(j, i) + f(j - 1, k - 1)
)
for k <= j <= i

We can precalculate a step to make the result for inversion_count(interval) O(1) time by using O(n^2) time and space: for all elements, e, in A, store how many smaller elements are in each interval that starts at e. When we decrease j in the main iteration, increasing the size of the interval, the number of inversions increases by the number of elements smaller than A[j] in the interval [j, i], which we've precalculated.

edited Dec 16, 2018 at 18:40

answered Dec 16, 2018 at 15:50

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Count maximum inversions for k subarrays

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related