Binary search is a general strategy that can often be applied to problems that seeks a single optimized number as an answer.

Let $A=[a_1, \cdots, a_n]$ be the given array of weights. Assume $1\lt n$ and $1\lt P\lt n$; otherwise, the problem becomes trivial.

Given a weight $w$ such that $\max a_i\le w\le\sum a_i$, we can associate a partition $\mathcal P(w)$, $A = P_1\,P_2\,\cdots P_m$ such that

1. Subarray $P_1$ is as long as possible such that the sum of all weights in it is no more than $w$.
2. Then subarray $P_2$ is as long as possible such that the sum of all weights in it is no more than $w$.
3. Then subarray $P_3$ is as long as possible such that the sum of all weights in it is no more than $w$.
4. And so on.
5. Finally, we are left with non-empty subarray $P_m$, the sum of all weights in which is no more than $w$.

Note that $m=\#\mathcal P(w)$ is the minimum number of segments in a partition where the sum of all weights in every segment is at most $w$. We want to find $w$ such that $\#\mathcal P(w)=P$ and $\#\mathcal P(w+1)<P$. Since the map from $w$ to $\mathcal P(w)$ is decreasing, we can use binary search to find it.

Here is the outline of an algorithm that finds the largest $w$ such that $\mathcal P(w)=P$. Assume the given weights are integers; otherwise, we need to tweak the algorithm a bit. .

1. If $P\gt\#\mathcal P(\max a_i)$, return "no such partition".

2. Let $low=\max a_i$ and $high=\sum a_i$.

3. If $low==high-1$, return $\mathcal P(low)$. Otherwise, let $ mid = (low + high)//2$ and compute $m= \#\mathcal P(mid)$.

   • If $m\ge P$, raise $low$ to $mid$.
   • If $m\lt P$, lower $high$ to $mid$.

4. Go back to step 2.

This algorithm runs in $O(n\log(\sum a_i))$ time, since it takes $O(n)$ time to compute $\mathcal P(w)$ for any given weight $w$.

Binary search is a general strategy that can often be applied to problems that seeks a single optimized number as an answer.

Let $A=[a_1, \cdots, a_N]$ be the given array of weights. Assume $1\lt P\lt N$; otherwise, the problem becomes trivial.

Given a weight $w$ such that $1\le w\le\sum a_i$, we can associate a partition $\mathcal P(w)$, $A = P_1\,P_2\,\cdots P_m$ such that

1. Subarray $P_1$ is as long as possible such that the sum of all weights in it is no more than $w$.
2. Then subarray $P_2$ is as long as possible such that the sum of all weights in it is no more than $w$.
3. Then subarray $P_3$ is as long as possible such that the sum of all weights in it is no more than $w$.
4. And so on.
5. Finally, we are left with non-empty subarray $P_m$, the sum of all weights in which is no more than $w$.

Note that $m=\#\mathcal P(w)$ is the minimum number of subarrays in a partition where the sum of all weights in every subarray is at most $w$. We want to find $w$ such that $\#\mathcal P(w)=P$ and $\#\mathcal P(w+1)<P$. Since the map from $w$ to $\mathcal P(w)$ is decreasing, we can use binary search to find it.

Here is the outline of an algorithm that finds the largest $w$ such that $\mathcal P(w)=P$. Assume the given weights are integers; otherwise, we need to tweak the algorithm a bit. .

1. Let $ma=\max\{a_i\}$. If $P\ge \#\mathcal P(ma)$, the least maximum sum is $ma$. Deal with this easy case and return.

2. Let $low=ma$ and $high=\sum a_i$.

3. If $low\lt high-1$, $ mid = (low + high)//2$ and compute $m= \#\mathcal P(mid)$.

   • If $m\le P$, lower $high$ to $mid$.
   • If $m\gt P$, raise $low$ to $mid$.

Go back to the start of this step.

1. Let $H$ be the partition $\mathcal P(high)$. If $\#H\not= P$, divide some subarrays of $H$ into smaller subarrays so as to increase the number of subarrays by $P-\#(P)$. Return $H$.

The loop invariant for step 3 is $\#\mathcal P(low)>P$, $\#\mathcal P(high)\le P$ and $low\le high-1$. When the loop ends, i.e., when $low==high-1$, we must still have $\#\mathcal P(low)>P$ and $\#\mathcal P(high)\le P$. That means, $high$ is the minimum of the maximum sum of weights of any subarray in a partition of size no more than $P$, which explains largely why this algorithm is correct.

This algorithm runs in $O(N\log(\sum a_i))$ time, since the most of time is spent on computing $\mathcal P(w)$ and it takes $O(N)$ time to compute $\mathcal P(w)$ for any given weight $w$.

Exercise (the dual problem). Given an array of $N$ positive integer weights $w_i$ and an integer $P$, divide the array into $P$ parts such that the parts are optimally balanced, i.e. that minimum sum of weights of any part is as large as possible.