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