Array Partitioning
You're working on a new feature for UptoSkills Arena that optimizes data storage. You have an array of N positive integers, representing data block sizes. You need to partition this array into K contiguous subarrays. Your goal is to minimize the maximum sum among all these K subarrays. Find this minimum possible value for the maximum sum.
Input
The first line contains two integers, N (the number of elements in the array) and K (the number of subarrays). The second line contains N positive integers representing the array elements.
Output
Print a single integer: the minimum possible value of the maximum sum among the K subarrays.
Constraints
1 <= N <= 200000 1 <= K <= N 1 <= a[i] <= 10^9
Example 1
5 2 7 2 5 10 8
18
The array can be partitioned into [7, 2, 5] and [10, 8]. The sums are 14 and 18. The maximum sum is 18. This is the minimum possible maximum sum. Another partition could be [7, 2] and [5, 10, 8] (sums 9, 23, max 23). Or [7] and [2, 5, 10, 8] (sums 7, 25, max 25).
Example 2
4 3 1 1 1 1
2
The array can be partitioned into [1], [1], [1, 1]. The sums are 1, 1, 2. The maximum sum is 2. Alternatively, [1, 1], [1], [1] also gives max sum 2.
Hints
Similar problems
- Minimum Maximum Height DifferenceMedium
- Maximize Minimum DifferenceMedium
- Minimize Maximum Segment SumMedium
- Max Consecutive SumMedium
- Maximum Sum of Non-Overlapping SubsegmentsMedium
- Maximum Sum of Non-Overlapping SegmentsMedium
More topics: Binary Search problems, Greedy problems, Dynamic Programming problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 2 7 2 5 10 8
4 3 1 1 1 1