Binary Search on AnswerDynamic ProgrammingGreedy
Split an array into m non-empty contiguous parts so that the largest sum among the parts is as small as possible. Print that minimised largest sum. (This is the same idea as allocating books to students or partitioning boards among painters.)
Input
Line 1: n and m. Line 2: n non-negative integers.
Output
Print the minimum possible value of the largest part sum.
Constraints
1 <= m <= n <= 1000 0 <= each value <= 10^6
Example 1
Input
5 2 7 2 5 10 8
Output
18
Split into [7 2 5] and [10 8]: the sums are 14 and 18, so the answer is 18.