Split array into contiguous subarrays of approximately same sums
This is a polynomial time algorithm:

Let $S^*_j$ be the sum of the the elements in the $j$-th subarray in an optimal solution and guess $m^* = \min_j S^*_j$ (there are only polynomially many choices of $m^*$).

Given a a way to split an array into $k$ contiguous subarrays of sums $S_1, \dots, S_k$, define the cost of such a subdivision as:
$$
\begin{cases}
 \max_i S_i &amp; \mbox{if } \min_i S_i \ge m^* \\
+\infty &amp; \mbox{ otherwise.}
\end{cases}
$$

Let $OPT_{m^*}[i,k]$ the cost to split the array consisting of the first $i$ input elements into $k$  contiguous (non-empty) subarrays, and let $x_i$ be the $i$-th input element.
Then, for $i,k \ge 1$,
$$
OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1} 
\begin{cases}
\displaystyle\max\, \left\{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \right\} &amp; \mbox{if } \displaystyle\sum_{h=j+1}^i x_i \ge m^* \\[10pt]
+\infty &amp; \mbox{otherwise}
\end{cases}.
$$

Where $OPT_{m^*}[0][0] = 0$ and $OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$ for all $i,k &gt; 0$.

The measure of an optimal solution to the original problem will be $OPT_{m^*}[n][N] - m^*$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $j$ chosen for each entry $OPT_{m^*}[i][k]$).