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?
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 &lt; i$. Then $A[n]$ contains your answer.