Maximum Balanced Shipments

medium monotonic stack dynamic programming greedy

Problem

You are given an array weight of n parcels in a line. A shipment is a contiguous subarray; it is balanced when the last parcel's weight is strictly less than the maximum weight in that shipment. Pick a set of non-overlapping balanced shipments (parcels may stay unshipped) and return the maximum number of shipments you can form.

Inputweight = [2, 5, 1, 4, 3]

Output2

Take [2, 5, 1] (max 5 > last 1) and [4, 3] (max 4 > last 3). Two balanced shipments — no partition does better.

weight (comma-separated, positive integers)

def maxBalancedShipments(weight):
    n = len(weight)
    stack = []                       # indices, weights strictly decreasing
    best = [0] * n                   # best[i] = max shipments using weight[0..i]
    for i in range(n):
        # pop indices whose weight cannot dominate weight[i]
        while stack and weight[stack[-1]] <= weight[i]:
            stack.pop()
        if stack:                    # nearest j < i with weight[j] > weight[i]
            j = stack[-1]
            take = (best[j - 1] if j > 0 else 0) + 1
        else:
            take = 0                 # no greater element: no shipment ends here
        carry = best[i - 1] if i > 0 else 0
        best[i] = max(carry, take)   # skip parcel i, or end a shipment at i
        stack.append(i)
    return best[n - 1]

function maxBalancedShipments(weight) {
  const n = weight.length;
  const stack = [];                  // indices, weights strictly decreasing
  const best = new Array(n).fill(0); // best[i] = max shipments using weight[0..i]
  for (let i = 0; i < n; i++) {
    // pop indices whose weight cannot dominate weight[i]
    while (stack.length && weight[stack[stack.length - 1]] <= weight[i]) {
      stack.pop();
    }
    let take = 0;
    if (stack.length) {              // nearest j < i with weight[j] > weight[i]
      const j = stack[stack.length - 1];
      take = (j > 0 ? best[j - 1] : 0) + 1;
    }
    const carry = i > 0 ? best[i - 1] : 0;
    best[i] = Math.max(carry, take); // skip parcel i, or end a shipment at i
    stack.push(i);
  }
  return best[n - 1];
}

int maxBalancedShipments(int[] weight) {
    int n = weight.length;
    Deque<Integer> stack = new ArrayDeque<>(); // indices, weights decreasing
    int[] best = new int[n];                   // best[i] = max using weight[0..i]
    for (int i = 0; i < n; i++) {
        // pop indices whose weight cannot dominate weight[i]
        while (!stack.isEmpty() && weight[stack.peek()] <= weight[i]) {
            stack.pop();
        }
        int take = 0;
        if (!stack.isEmpty()) {                // nearest j with weight[j] > weight[i]
            int j = stack.peek();
            take = (j > 0 ? best[j - 1] : 0) + 1;
        }
        int carry = i > 0 ? best[i - 1] : 0;
        best[i] = Math.max(carry, take);       // skip parcel i, or end here
        stack.push(i);
    }
    return best[n - 1];
}

int maxBalancedShipments(vector<int>& weight) {
    int n = weight.size();
    vector<int> stack;                  // indices, weights strictly decreasing
    vector<int> best(n, 0);             // best[i] = max shipments using weight[0..i]
    for (int i = 0; i < n; i++) {
        // pop indices whose weight cannot dominate weight[i]
        while (!stack.empty() && weight[stack.back()] <= weight[i]) {
            stack.pop_back();
        }
        int take = 0;
        if (!stack.empty()) {          // nearest j with weight[j] > weight[i]
            int j = stack.back();
            take = (j > 0 ? best[j - 1] : 0) + 1;
        }
        int carry = i > 0 ? best[i - 1] : 0;
        best[i] = max(carry, take);    // skip parcel i, or end a shipment at i
        stack.push_back(i);
    }
    return best[n - 1];
}

Explanation

A shipment is balanced exactly when its last parcel is not the unique heaviest — some earlier parcel inside it is strictly heavier. So a balanced shipment that ends at index i must contain an earlier index whose weight exceeds weight[i].

The cheapest such shipment starts at j, the nearest previous index with a strictly greater weight. Starting exactly at j uses the fewest parcels while still guaranteeing the maximum beats weight[i], which leaves the longest possible prefix [0 .. j-1] free for more shipments. That is a clean greedy choice.

To find each j in linear time we keep a monotonic stack of indices with strictly decreasing weights. Before processing i we pop every index whose weight is ≤ weight[i]; whatever remains on top is exactly the nearest strictly-greater element. If the stack empties, no earlier parcel beats weight[i], so no balanced shipment can end at i.

Let best[i] be the most shipments achievable using only parcels 0 .. i. At each i we either skip parcel i (best[i-1]) or end a shipment [j .. i] and add the answer for the prefix before it (best[j-1] + 1). We take the larger. The final answer is best[n-1].

Example [2, 5, 1, 4, 3]: at the 1 the nearest greater is the 5 at index 1, giving shipment [5, 1]... but extending left to [2, 5, 1] is the same count, so best becomes 1. At the final 3 the nearest greater is the 4, shipment [4, 3], and best[1] + 1 = 2. Answer: 2.

Time: O(n) Space: O(n)