algorithm - How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?

Question

The inputs are an array A of positive or null integers and another integer K.

We should partition A into K blocks of consecutive elements (by "partition" I mean that every element of A belongs to some block and 2 different blocks don't contain any element in common).

We define the sum of a block as sum of the elements of the block.

The goal is to find such a partition in K blocks such that the maximum of the sums of each block (let's call that "MaxSumBlock") is minimized.

We need to output the MaxSumBlock (we don't need to find an actual partition)

Here is an example:

Input:

A = {2, 1, 5, 1, 2, 2, 2}
K = 3

Expected output:

MaxSumBlock: 6
(with partition: {2, 1}, {5, 1}, {2, 2, 2})

In the expected output, the sums of each block are 3, 6 and 6. The max is 6.

Here is an non optimal partition:

partition: {2, 1}, {5}, {1, 2, 2, 2}

The sums of each block in that case are 3, 6 and 7. The max is hence 7. It is not a correct answer.

What algorithm solves this problem?

EDIT: K and the size of A is no bigger than 100'000. Each element of A is no bigger than 10'000

Answer 1

Use binary search.

Let max sum range from 0 to sum(array). So, mid = (range / 2). See if mid can be achieved by partitioning into k sets in O(n) time. If yes, go for lower range and if not, go for a higher range.

This will give you the result in O(n log n).

PS: if you have any problem with writing the code, I can help but I'd suggest you try it first yourself.

EDIT:
as requested, I'll explain how to find if mid can be achieved by partitioning into k sets in O(n) time.
Iterate through the elements till sum is less than or equal to mid. As soon as it gets greater than mid, let it be part of next set. If you get k or less sets, mid is achievable, else not.