What problem is this? Largest sum produced by selecting one number at each index from n lists, with restrictions

Question

Suppose you have an $n\times m$ 2D array consisting of each $n$ rows of $m$ real numbers. What is the sequence of indexes $i_1,i_2...i_m$ such that $\sum_{j=1}^mA[i_j, j]$ is maximized, subject to the constraint that each run of a value in $i_1...i_m$ must be at least $r$ entries long?

A correct algorithm with time linear in $m$ seems possible with dynamic programming. It would be even nicer to know the name of the problem and some academic reference to a correct solution. This is a minor methodological step in an analysis I'm doing for an interpersonal communication research paper, so ideally I'd like to find a paper to cite. This smells very similar to the dynamic programming homework problems I did in undergrad, so I'd be surprised if there isn't work on it.

In practice, $m \approx 12000$, $n=3$, and $20 \leq r \leq 200$.

Answer 1

I believe this can be solved in $O(nm)$ time using dynamic programming:

$$\begin{align*} B[i,k] &= A[i,k] + \dots + A[i,k+r-1] + C[i,r]\\ C[i,k] &= \max(A[i,k] + C[i,k+1], \max_{i'} B[i',k]) \end{align*}$$

Note that you can compute $A[i,k] + \dots + A[i,k+r-1]$ in $O(1)$ time as the difference of two prefix sums (assuming you have done a one-time precomputation to compute all prefix-sums).

The answer is then $\max_i B[i,1]$. Computing it takes $O(nm)$ time, as there are $O(nm)$ entries to fill in, and each one takes $O(1)$ time to fill in, using the equations above.

Interpretation:

• $B[i,k]$ is the maximum possible value of $\sum_{j=k}^m A[i_j,j]$ such that $i_k=i$ and $i_k,\dots,i_m$ satisfy the repetition rule

• $C[i,k]$ is the maximum possible value of $\sum_{j=k}^m A[i_j,j]$ such that $i_k,\dots,i_m$ satisfy the repetition rule except that if $i_k=i$, the run starting at $i_k$ can be of any length (but all subsequent runs must be at least $r$ long). In other words, $$C[i,k] = \max_\ell A[i,k] + \dots + A[i,k+\ell-1] + \max_{i'} B[i',k+\ell]$$

Generally, this is not the kind of thing I would expect to find papers about. I would expect to see a one-sentence "can be solved by dynamic programming", possibly with an explanation of the max-trick above to reduce the running time from $O(nmr)$ to $O(nm)$, but not an entire paper about it. So I would not bet on such a paper existing. But I could be wrong. It's certainly possible there could be such a paper. I would not know how to go about looking for it.