3638. 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.

class Solution {
public:
    int maxBalancedShipments(vector<int>& weight) {
        int res = 0, n = weight.size();
        for(int i = 1, best = weight[0]; i < n; i++) {
            if(best > weight[i]) {
                res++;
                if(i + 1 < n) best = weight[++i];
            } else best = weight[i];
        }
        return res;
    }
};