1
$\begingroup$

I have a sequence of points $(x_1, \ldots, x_n)$ and a function $f$ that maps every consecutive subsequence (ie. of the form $(x_i, x_{i+1}, \ldots, x_j)$) to a real number. I want to split this sequence into partitions of consecutive subsequences so that the sum of $f$ on each partition is maximized.

For example, suppose the sequence is $(1, 5, 6)$ and $f$ is defined as: $f(1) = 1, f(1,5) = 13, f(1,5,6) = 0, f(5) = 2, f(5,6) = 9, f(6) = 6$

Then partitioning the sequence as $\{(1,5), (6)\}$ achieves the maximum possible value of $f(1,5) + f(6) = 19$.

Is this problem NP-hard? I can come up with some greedy algorithms to find an approximate solution, but I don't think they always get the correct answer. But I can't figure out how to prove that it's NP-hard either. Any hints on how to make the reduction?

$\endgroup$
  • $\begingroup$ Please add a reference to the original problem. 1) Credit should be attributed. 2) A reference is apt to motivate people. 3) A reference may save readers who look for related materials lots of time. $\endgroup$ – Apass.Jack Feb 2 at 4:58
7
+50
$\begingroup$

This problem can be solved in polynomial time with dynamic programming. Let $A[i]$ be the maximum value you can achieve with the points $x_1, \dots, x_i$.

You can compute $A[i]$ by choosing the maximum of $A[k]$ + $f(x_{k+1}, x_{k+2}, \dots, x_i)$ from all $k < i$. Then $A[n]$ contains your answer.

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