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

• 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$. – Pål GD Sep 30 '13 at 19:38
• 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 Sep 30 '13 at 19:55
• It might haven't been clear before, so I specified that subarrays should be contiguous. – Arek Holko Sep 30 '13 at 20:18

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