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

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

• If there is a simple dynamic programming algorithm for this problem, I wouldn't expect there to be a paper about it; that's not the sort of thing that tends to get published. Most problems don't have a "name". The obvious dynamic programming algorithm I can see seems to take $O(nm)$ time rather than $O(m)$ time. – D.W. Feb 2 at 0:13
• Certainly no recent paper, but wouldn't there be some similar problem in the early days? If not, that's not bad - I just brush off my proof-writing skills and add a proof in the supplementary material for the article submission. I'm concerned there is one but I don't know it. And you're absolutely right. The important part is that it's not O(m^2) or O(2^m) or O(m choose m/r) - just that the m term is linear. Is there a more technical way to say that? – Mark Miller Feb 2 at 1:25
• Also, my sketch was O(nmr) rather than O(nm) - perhaps can you share your sketch? – Mark Miller Feb 2 at 1:26

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.

• The answer of "there probably isn't a paper" is still helpful. On top of that, the difference of prefix sums is an insight I wouldn't have gotten in this case. One note, though - is the expression for B rather $B[i, k] = A[i,k] + \dots + A[i,k+r-1] + \max_{i'} C[i', r]$? I think I follow everything else. – Mark Miller Feb 3 at 2:10
• @MarkMiller, oh, right, that was wrong, thank you! Edited. I think the expression is a little different, maybe. – D.W. Feb 3 at 4:38