# Is this partitioning problem NP-complete?

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?

• 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. – John L. Feb 2 '19 at 4:58

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.