Clash Royale CLAN TAG#URR8PPP

Maximum value of sum of K partitioned subarrays

Given a subarray of an array, its value is the maximum of the elements it contains that appear an odd number of times.

I want to Partition an array into K sub arrays to maximize the sum of the subarray values.

E.g. if we have following array

5 6 6 3 9 with K=2

We could partition it as follows:

(5) + (6,6,3,9) = (5 + 9 => 14 )

(5,6) + (6,3,9) = ( 6 +9 => 15 )

(5,6,6) + (3,9) = ( 5 + 9 =>14 )

(5,6,6,3) + (9) = ( 5 + 9 => 14 )

I am able to do it the brute way but looking for an efficient algorithm. Could you please suggest something

3 Answers
3

The algorithm I see is quite easy. You need to find positions of K maximum values in the array and then divide array in the way that these positions are in different subarrays in the way that max value is included the odd number of times in each subarray. Need to specifically look into the last case. One of the options is trying to get the first one if K limit is reached.

So, for (6,6,6) and K=2 the algorithm should be:
Find 2 max elements (if K limit is reached, take the first K). In our case, it's first and second 6.
Then divide into subarrays (from max to nextMax-1)

(6) + (6,6) => 6


Quite an interesting case is (6,7,6,6) and K=3
The expected result is

(6) + (7,6) + (6) = 19


My algorithm doesn't cover that case

Pseudocode:

1. indexes = FindKMaxIndexes() // Use selection algorithm https://en.wikipedia.org/wiki/Selection_algorithm, some variation to save indexes instead of elements values
2. reorder indexes from smallest to largest
3. i = 0
4. for each item in sorted indexes array
4.1 create subarray to include item (from i to current index)
4.2 i = current index + 1


Actually the question seems like what the sum of maximum K number is. So just need to order by descending and sum the first K number.

Clearly, we can have O(n^2 * k) since if f(i, k) represents the maximum achievable up to A[i] with k parts, then:

O(n^2 * k)

f(i, k)

A[i]

k

f(i, k) = max(
// include A[i] in previous part
g(A[j..i]) + f(j - 1, k - 1),

// don't include A[i] in previous part
A[i] + f(i - 1, k - 1)
)
for all k <= j < i
where g(subarray) is the max element
in subarray that appears an odd number
of times


The question is how can we more efficiently pick which subarrays to test including A[i] against.

A[i]

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.