How can I improve my algorithm for finding optimally balanced P-way partitioning of array
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 


Subarray $P_1$ is as long as possible such that the sum of all weights in it is no more than $w$. 
Then subarray $P_2$ is as long as possible such that the sum of all weights in it is no more than $w$.
Then subarray $P_3$ is as long as possible such that the sum of all weights in it is no more than $w$.
And so on.
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)&lt;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. .


Let $ma=\max\{a_i\}$. If $P\ge \#\mathcal P(ma)$, the least maximum sum is $ma$. Deal with this easy case and return. 
Let $low=ma$ and $high=\sum a_i$. 
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.
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)&gt;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)&gt;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.