Partition a 3 * K array to K equal subarrays algorithm

Question

I need to Partition N elements array to K equal subarrays of 3 elements each algorithm in order to find the max sum of the 2nd element of these triplets sorted.

6 <= N <= 300 

K = number of triplets

K * 3 = N

an example would be:

N = 5,8,1,5,1,2,7,2,9

Will create three triplets sorted: 1,5,7 1,2,5 2,8,9

that gives us the maximum result of all possible triplets ( 5 + 2 + 8 ) = 15

I know this can be solved by DP techniques but I wonder if it can be solved in other ways (more efficient)?

Answer 1

The greedy algorithm is provably optimal.

Start by sorting the array, so it's [1, 1, 2, 2, 5, 5, 7, 8, 9]. Then build triples so as to maximise the middle element in the triple. The third element must be >= the middle element, so we pick the largest two values along with the smallest one.

• The two largest values are 8 and 9, so the first triple is 1, 8, 9.
• The two remaining largest values are 5 and 7, so the next triple is 1, 5, 7.
• The two remaining largest values are 2 and 5, so the last triple is 2, 2, 5.

This gives a total sum of 8 + 5 + 2 = 15. Note that we don't need to actually produce the partitions; after sorting the list, the K middle elements are those at indices N-2, N-4, ..., N-2K, so we can just find their sum directly:

[1, 1, 2, 2, 5, 5, 7, 8, 9]
          ↑     ↑     ↑

---

Now let's prove you can't do better. Any partition ends up with K arrows pointing at elements of the sorted array. Each arrow must be paired with a non-arrow at a greater index, otherwise it is not the middle element from a triple, or otherwise the third element from its triple has already been used in another triple. So the density of arrows in any suffix of the array cannot exceed 1/2. Conversely, any assignment of arrows with this suffix density property is achievable as a partition, by Hall's marriage theorem.

Consider an assignment of arrows to array indices. If the pattern ↑ _ _ occurs, move the arrow one space to the right:

[..., x, y, z, ...]
 ...  ↑  _  _  SSS

becomes

[..., x, y, z, ...]
 ...  _  ↑  _  SSS

This does not decrease the sum of numbers-with-arrows because x <= y; and it leaves the density of all suffixes the same except the suffix starting at y. The suffix starting at y has A+1 arrows and U+1 non-arrows, so its density is <= 1/2 if and only if A+1 <= U+1. This holds because SSS's density is <= 1/2 implying A <= U.

It follows that the pattern ↑ _ ↑ _ ↑ _ cannot be improved on by moving some arrow to the right (since it would violate the density restriction), nor by moving some arrow to the left (since it would create a ↑ _ _).

Answer 2

The first step seems to be to sort the array.

The lowest best element to take is the element at position K + 1 (index K), because you put the K lowest ones as first element in each array and then you have to put the element at position K + 1 at the 2nd position of one of the arrays.

The highest number is the element at position N - 1 (index N - 2), this happens if you put the 2 highest elements in one array. This is also optimal, because if you spread those high numbers among more than one array, you will just lose value without any gain.

Finally for the numbers in the middle: We can get the best value again by using the next 2 highest elements (those we haven't used yet).

So the solution is to take the elements at indexes [N - 2, N - 4, N - 6, ... , K]

Or in code, time complexity O(nlogn) because of the sort, although you could theoretically get O(n) if the numbers have an upper bound (i.e. fixed number of bits) by using radix sort:

public int bestSum(int[] arr) {
    int sum = 0;
    Arrays.sort(arr);
    for (int i = 1; i <= arr.length / 3; i++)
        sum += arr[arr.length - 2 * i];
    return sum;
}