1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – D.W. Feb 2 at 0:13
  • $\begingroup$ 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? $\endgroup$ – Mark Miller Feb 2 at 1:25
  • $\begingroup$ Also, my sketch was O(nmr) rather than O(nm) - perhaps can you share your sketch? $\endgroup$ – Mark Miller Feb 2 at 1:26
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Mark Miller Feb 3 at 2:10
  • $\begingroup$ @MarkMiller, oh, right, that was wrong, thank you! Edited. I think the expression is a little different, maybe. $\endgroup$ – D.W. Feb 3 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.