Split array into contiguous subarrays of approximately same sums

My question is similar to this splitting question, but my objective function is different.

Looking for an algorithm to split array of $n$ positive (integer) numbers into $N$ contiguous non-empty subarrays ($N<n$) of approximately same sums:

$$
\min_{\text{splits}} \,(\max_j S_j - \min_j S_j),
$$
where $S_j$ is sum of numbers in $j$-th subarray $(j=1,\ldots,N)$.

E.g., best splitting of $100, 1, 1, 103, 90$ into three subarrays is $100,1,1|103|90$.

Typically $n\approx~10^6-10^8$, $N\approx 10-100$.

I suspect it would be some greedy approach...

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 & \mbox{if } \min_i S_i \ge m^* \\
+\infty & \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\} & \mbox{if } \displaystyle\sum_{h=j+1}^i x_i \ge m^ \\[10pt]
+\infty & \mbox{otherwise}
\end{cases}.
$$

Where $OPT_{m^}[0][0] = 0$ and $OPT_{m^}[i][0] = OPT_{m^*}[0][k] = +\infty$ for all $i,k > 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]$).

StackExchange Computer Science Q#110233, answer score: 2