# Maximizing some type of inner product

For positive integers $$n,m,k$$, you're given a vector $$c\in\mathbb{N}^n$$ and a set $$\Omega$$ of $$k$$ finite non-empty sequences of numbers from $$\{1,\dots,m\}$$. You're asked to choose $$\sigma_1\lt\sigma_2\lt\ldots\lt\sigma_\ell$$ in $$\{1,\ldots,n\}$$ and $$\varphi\colon\{1,\ldots,\ell\}\rightarrow\Omega$$ such that, $$\begin{eqnarray} (1)\quad\forall i\in\{1,\ldots,\ell\},\quad \sigma_{i+1}-\sigma_i\ge |\varphi(i)| \end{eqnarray}$$ then, you're rewarded $$r$$ dollars where,
$$$$r = \sum_{1\le i\le\ell}\,\,\sum_{0\le j\lt|\varphi(i)|}c(i+j)\varphi(i)_j$$$$ Question: is there a known algorithm for computing the max of $$r$$ over the choices of $$\sigma$$'s and $$\varphi$$?

Comments: In other terms, you're asked to build a vector $$x\in\mathbb{N}^n$$ where a subset of sequences in $$\Omega$$ are laid out in a non-overlapping fashion such that the inner product $$c\cdot x$$ is maximized (non-occupied site of $$x$$ are set to $$0$$). More precisely, you're asked to compute $$\begin{eqnarray} \max_x c\cdot x. \end{eqnarray}$$

Notation:

• $$|\varphi(i)|$$ denotes the length of the sequence $$\varphi(i)$$.
• $$\varphi(i)_j$$ denotes the $$j$$-th term of the sequence $$\varphi(i)$$.
• For correctness of $$(1)$$, let $$\sigma_{\ell+1}=n+1$$.