Given an array of $N$ elements, $A$, and a number $K$. ($1 \leq K \leq N$) .
Partition the given array into $K$ subsets (they must cover all the elements but can be noncontiguous too). The maximum subset sum achievable out of $K$ partitions formed, must be the minimum possible.
Find that possible subset sum.
For example $A = [11, 11, 5, 10, 5]$ and $K = 2$ the partitioning that satisfies the problem will be $\{\{11, 5, 5\}, \{11, 10\}\}$ so that the defined maximum sum will be $21$ and it is the minimum of all different K-Partitionings of $A$.
The question came up to my mind when I was solving a similar problem for only K contiguous subarrays which could be easily solved using a binary search over all possible maximum sums of the array($O(\log{\text{SUM}})$).
For example for the same $A$ defined in above maximum sum is at least the maximum number which is $11$ and is at most the total sum of all elements which is $42$.
Then in each step of binary search we check whether it is possible to split $A$ into at most $K$ contiguous subarrays or not so that the maximum sum over all subarrays will be at most the mid point of binary search step(needs one loop over $A$ then $O(n)$). If yes we recurse on the left side, otherwise we recurse on the right side.
in overall the algorithm will have a $O(n\log{\text{SUM}})$ time complexity.
But I can't find a way to generalize the checking process in every step of the binary search so that it checks whether for a specific maximum sum like $s^{*}$ is it possible to partition $A$ with at most $K$ subsets so that the maximum sum over all subsets will be at most $s^{*}$ with a good time complexity.
I should also mention that the above motivation is not necessarily the only way accepted to solve this problem and every other idea will be appreciated.
