Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

6
  • $\begingroup$ I believe you mean "the smallest $L$ for which, for all $k$, $is\_there[k, t, L] = false$. If you only require that it hold for "some" $k$, then $is\_there[k', t, L]$ could be true for some $k' \ne k$, which would break the requirements. $\endgroup$ Commented Sep 17, 2017 at 20:33
  • $\begingroup$ I think there is another problem: in the second branch of the $\land$, checking just $is\_there[k-1, m-1, L-1]$ forces $X_{m-1}$ into the subsequence, when we should allow the length-$(L-1)$ subsequence to end at any character at or before $X_{m-1}$. This could be fixed, without hurting the asymptotic running time, by defining $is\_there\_any[k, m, L] = is\_there[k, m, L] \lor is\_there\_any[k, m-1, L]$, and using $is\_there\_any[k-1, m-1, L-1]$ in the DP recurrence instead. $\endgroup$ Commented Sep 17, 2017 at 21:22
  • $\begingroup$ @j_random_hacker: I think you are right. Would you like to edit the answer as you please? $\endgroup$ Commented Sep 18, 2017 at 19:53
  • 1
    $\begingroup$ Done! (Pad, pad, pad.) $\endgroup$ Commented Sep 18, 2017 at 20:08
  • $\begingroup$ is_there does not have a halting condition. $\endgroup$ Commented Oct 29, 2017 at 19:33