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