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

Problem Detail: 

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.

Asked By : Arek Holko

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14713