Find the minimum ship capacity needed to deliver all packages within a fixed number of days while keeping package order unchanged.
You are given an array of package weights, where each weight represents the mass of one package in the order it must be loaded. A ship loads packages in that same order, and on each day it can carry a contiguous sequence of packages whose total weight does not exceed its capacity.
Your task is to determine the minimum ship capacity needed so that all packages can be shipped within exactly or at most days.
Because the packages must be loaded in order, you cannot reorder them to make shipping easier. If the capacity is too small, shipping will take too many days; if it is large enough, all packages can be delivered on time.
Input Format
Input
- An integer array
weightswhereweights[i]is the weight of the -th package. - An integer
daysrepresenting the maximum number of days allowed.
Assumptions
- Packages must be shipped in the given order.
- Each day, the ship can load a contiguous prefix of the remaining packages until adding the next package would exceed the ship capacity.
Output Format
Output
- Return the minimum integer ship capacity that allows all packages to be shipped within
daysdays.
Constraints
- The answer fits in a 32-bit signed integer.
Example 1
Input
weights = [1,2,3,1,1], days = 4
Output
3
Explanation
With capacity 3, the ship can load [1,2], [3], [1,1], and then one package per day if needed; all packages are delivered within 4 days. A smaller capacity would require more than 4 days.
Example 2
Input
weights = [3,2,2,4,1,4], days = 3
Output
6
Explanation
One optimal loading plan is [3,2], [2,4], [1,4]. Each day's load is at most 6, so 6 is the minimum feasible capacity.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.