Algorithm for splitting array into subarrays with sums close to the target value I have an array of positive integers, $A = (a_1, a_2, ..., a_n)$.
Let $s(A)$ denote the sum of elements of array $A$.
I also have an integer $t$, such that $1 &lt; t \le s(A)$.

I want to split the array $A$ into $m$ contiguous subarrays $(A_1, ..., A_m)$, for which I'll get a minimum of function $f$, defined as

$$
f(A_1, ..., A_m) = \sum_{1 \le i \le m}{(s(A_i) - t)^2}.
$$

Please note that I'm talking specifically about arrays, so the order of elements does matter.

Here is a simple example.

Let $t = 13$ and
$$
A = (1, 6, 7, 10, 3, 2, 10).
$$
With the following subarrays
$$
A_1 = (1, 6, 7)\\
A_2 = (10, 3) \\
A_3 = (2, 10) \\
$$
the value of $f(A_1, A_2, A_3) = (14-13)^2 + (13 - 13)^2 + (12 - 13)^2 = 2$.

I don't need an exact solution. Good heuristic would be sufficient.
You can solve it exactly using dynamic programming, though that might be too slow or might require too much memory. Calculate an array $B(\ell,k)$, which is the minimal error obtained by dividing $a_1,\ldots,a_k$ into $\ell$ parts. This can be implemented in time and space $O(mn)$ by calculating (in advance) the running sums $\sum_{i \leq t} a_i$.