Maximum Balanced Shipments
You are given an integer array weight of length n, representing the weights of n parcels arranged in a straight line.
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: 2
Explanation: We can form the maximum of two balanced shipments as follows: It is impossible to partition the parcels to achieve more than two balanced shipments, so the answer is 2.
Example 2
Input: weight = [4,4]
Output: 0
Explanation: No balanced shipment can be formed in this case: As there is no way to form even one balanced shipment, the answer is 0.
Constraints
- 2 <= n <= 10^5
- 1 <= weight[i] <= 10^9
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.