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
