Algorithm for splitting array into subarrays with sums close to the target value

Question

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ドル < 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.

• Ainsley H.: Is a two-approximation good enough? Can you think of a greedy algorithm? How far off can the natural greedy algorithm be? Ps., this is NP-hard even for $m=3$.
• Arek Holko: I think factor 2 approximation should be good enough. I stumbled on this problem during development of commercial application, so I'd have to run some tests and assess the results.
• Arek Holko: It might haven't been clear before, so I specified that subarrays should be contiguous.

Answer 1

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$.