Maximum Balanced Shipments
You are given an integer array weight of length n, representing the weights of n parcels arranged in a straight line. A shipment is defined as a contiguous subarray of parcels. A shipment is considered balanced if the weight of the last parcel is strictly less than the maximum weight among all parcels in that shipment.
Select a set of non-overlapping, contiguous, balanced shipments such that each parcel appears in at most one shipment. Parcels may remain unshipped.
Return the maximum possible number of balanced shipments that can be formed.
Example 1
Input
weight = [2,5,1,4,3]Output
2The maximum of two balanced shipments can be formed as
[2, 5, 1] and [4, 3], and it is impossible to form more than two.Example 2
Input
weight = [4,4]Output
0No contiguous shipment has a last parcel whose weight is strictly less than the maximum weight in that shipment.
Constraints
- 2 <= n <= 10^5
- 1 <= weight[i] <= 10^9
Asked at 1 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.