3954. Maximum Balanced Shipments¶

Input: weight = [2,5,1,4,3]

Output: 2

Explanation:

We can form the maximum of two balanced shipments as follows:

• Shipment 1: [2, 5, 1]
  • Maximum parcel weight = 5
  • Last parcel weight = 1, which is strictly less than 5. Thus, it's balanced.
• Shipment 2: [4, 3]
  • Maximum parcel weight = 4
  • Last parcel weight = 3, which is strictly less than 4. Thus, it's balanced.

It is impossible to partition the parcels to achieve more than two balanced shipments, so the answer is 2.

Input: weight = [4,4]

Output: 0

Explanation:

No balanced shipment can be formed in this case:

• A shipment [4, 4] has maximum weight 4 and the last parcel's weight is also 4, which is not strictly less. Thus, it's not balanced.
• Single-parcel shipments [4] have the last parcel weight equal to the maximum parcel weight, thus not balanced.

As there is no way to form even one balanced shipment, the answer is 0.

class Solution {
    public int maxBalancedShipments(int[] arr) {
        int n = arr.length;
        int currMaxi = -1, count = 0;
        for (int i = 0; i < n; i++) {
            if (currMaxi == -1) currMaxi = arr[i];
            else {
                if (arr[i] < currMaxi) {
                    count++;
                    currMaxi = -1;
                }
                else currMaxi = Math.max(currMaxi, arr[i]);
            }
        }
        return count;
    }
}