4
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.