<p>I think this can be solved in PTIME by a rather standard dynamic programming approach.</p>
<p>Define a table <span class="math-container">$T$</span> storing, for each prefix length <span class="math-container">$i$</span>, for each distance <span class="math-container">$j$</span>, for each sequence length <span class="math-container">$l$</span>, the maximum weight of a subsequence of the prefix of length <span class="math-container">$i$</span> of the input sequence such that the latest selected element is at distance <span class="math-container">$j$</span> from the end of the prefix (i.e., letting <span class="math-container">$x$</span> the latest selected element, <span class="math-container">$i-x = j$</span>), and the number of selected elements is <span class="math-container">$l$</span>. Initialize all cells to <span class="math-container">$-\infty$</span>.</p>
<p>The table is of polynomial size as it has at most <span class="math-container">$n^3$</span> cells.</p>
<p>Now, we can compute the values for <span class="math-container">$i+1$</span> from the values for <span class="math-container">$i$</span>, i.e., for each <span class="math-container">$i,j,l$</span>, if <span class="math-container">$j$</span> is sufficiently small to satisfy condition 2, update <span class="math-container">$T[i+1,0,l+1]$</span> to take the max of its current value and of the <span class="math-container">$i$</span>-th value plus <span class="math-container">$T[i,j,l]$</span> (intuitively, we add the leftmost element to the sequence), and update <span class="math-container">$T[i+1,j+1,l]$</span> to take the max of its current value and of <span class="math-container">$T[i,j,l]$</span> (intuitively, we do not add the leftmost element to the sequence).</p>
<p>This should satisfy the inductive invariant given in the first paragraph, and your desired answer would be the max of <span class="math-container">$T[n,j,l]$</span> over all suitable values of <span class="math-container">$j$</span> and all <span class="math-container">$l \leq t$</span>. This algorithm runs in polynomial time.</p>
<p>(I hope this is clear and I didn't misunderstand your problem.)</p>

CC BY-SA 4.0
2022-12-07T18:20:12.817Z
2022-12-07T18:20:12.817Z
Antoine Amarilli 'a3nm'
<p>Following the suggestion by Manuel Lafond, you can build a table with <span class="math-container">$O(n^2)$</span> entries.
Entry <span class="math-container">$M(i,k)$</span> contains the maximum sum of a valid subsequence of elements <span class="math-container">$\{\alpha_1, \ldots, \alpha_i\}$</span> of length <span class="math-container">$k$</span> and such that the last element of the subsequence is <span class="math-container">$\alpha_i$</span>.</p>
<p>Note that, trivially, <span class="math-container">$M(i, 1) = \alpha_i$</span> for all <span class="math-container">$i \in \{1,\ldots,n\}$</span>.</p>
<p>Also note that if a subsequence of length <span class="math-container">$k$</span> ends at <span class="math-container">$\alpha_i$</span>, then there must be at least another element among <span class="math-container">$\{\alpha_{i-d}, \ldots, \alpha_{i-1}\}$</span> in position <span class="math-container">$k-1$</span> in the subsequence. Otherwise, the &quot;no gap&quot; condition would be violated.
From this last observation, you can derive the Dynamic Programming recursion:
<span class="math-container">$$M(i, k) = \max_{i'=[i-d], \ldots, i-1} \{ M(i', k-1) \} + \alpha_i$$</span>
where <span class="math-container">$[i-d] = \max \{ 1, i-d \}$</span>.</p>
<p>Finally, there is a subsequence of length at most <span class="math-container">$t$</span> with a sum of at least <span class="math-container">$\beta$</span> if:
<span class="math-container">$$\min \biggl\{ k=1,\ldots,n \; \bigl|\bigr. \; \exists i \in \{k,\ldots,n\} \text{ s.t. } M(i,k) \geq \beta \biggr\} \leq t$$</span></p>
<p>Interestingly, I stumbled across the same problem very recently, in the context of a special case of the min-Knapsack Problem (in which the <span class="math-container">$\alpha_i$</span> are weights, <span class="math-container">$\beta$</span> is the capacity and profits are all unitary).</p>

CC BY-SA 4.0
2022-12-08T19:28:19.490Z
2022-12-08T22:43:49.190Z
2022-12-08T22:43:49.190Z
Alberto Santini
<p>Here is yet another &quot;is <em>X</em> NP-hard?&quot; question.</p>
<p>The input of the problem is the following:</p>
<ul>
<li>A sequence of <span class="math-container">$n$</span> non-negative real numbers <span class="math-container">$\alpha_1, \ldots, \alpha_n$</span>. Here <span class="math-container">$n$</span> is a positive natural number. If it makes any difference, I would also be fine with the assumptions that the <span class="math-container">$\alpha$</span>'s are integers instead of reals.</li>
<li>A non-negative real number <span class="math-container">$\beta$</span>. (Again, this number could be integer if it makes any difference.)</li>
<li>An integer number <span class="math-container">$d$</span> such that <span class="math-container">$1 \leq d &lt; n$</span>.</li>
<li>An integer number <span class="math-container">$t$</span> such that <span class="math-container">$1 \leq t \leq n$</span>.</li>
</ul>
<p>The problem asks whether there is a subsequence of <span class="math-container">$(\alpha _1, \ldots, \alpha_n)$</span> of length at most <span class="math-container">$t$</span> such that:</p>
<ol>
<li>The sum of the elements in the subsequence is at least <span class="math-container">$\beta$</span>. I.e., if the subsequence is <span class="math-container">$\alpha_{i_1}, \ldots, \alpha_{i_t}$</span>, then <span class="math-container">$\sum_{j=1}^t \alpha_{i_j} \geq \beta$</span>.</li>
<li>There is no gap larger than <span class="math-container">$d$</span> in the subsequence. For example, if a number <span class="math-container">$\alpha_i$</span> is in the subsequence, it cannot happen than none of the numbers <span class="math-container">$\alpha_{i-d}, \ldots, \alpha_{i-1}, \alpha_{i+1}, \ldots, \alpha_{i+d}$</span> are in the sub-sequence. In other words, if two numbers <span class="math-container">$\alpha_i$</span>, <span class="math-container">$\alpha_j$</span> are in the subsequence and <span class="math-container">$j &gt; i + d$</span>, then there must be at least another number in the subsequence among <span class="math-container">$\alpha_{i+1}, \ldots, \alpha_{j-1}$</span>.</li>
</ol>
<p>I spent quite some time on it, but I could not come up with any reduction from NP-complete problems I am familiar with.
At the same time, I do not have a polynomial-time algorithm for it.
The best I have is a pseudopolinomial-time dynamic programming algorithm which runs in <span class="math-container">$O(n \beta)$</span> (when <span class="math-container">$\beta$</span> is integer).</p>

CC BY-SA 4.0
2022-12-04T16:33:55.447Z
Have you looked at longest increasing subsequence and similar problems?  The dynamic programming ideas from there might be adaptable.  For instance, if you define $M(i, k)$ as the maximum sum achievable in $\alpha_1, \ldots \alpha_i$ with the restriction that $\alpha_i$ is the $k$-th number in the subsequence, then maybe you can calculate $M(i, k)$ in terms of $M(i - 1, k - 1), \ldots, M(i - d, k - 1)$.
Manuel Lafond
CC BY-SA 4.0
2022-12-05T03:43:46.390Z
Your two versions of condition 2 are not equivalent.  Which one did you intend?
D.W.
CC BY-SA 4.0
2022-12-06T22:52:08.100Z
Also, the first definition used in condition 2 seems to count a subsequence like $\alpha_1, \alpha_2, \alpha_{n-1}, \alpha_{n}$ as having no gaps > 1 since for each $\alpha$ there is another within distance 1.
mhum
<np-hardness><np-complete>
Is this subsequence problem NP-hard?
Qalat
# Is this subsequence problem NP-hard?

(Asked by: username_0 on 2022-12-04)

Here is yet another "is *X* NP-hard?" question.

The input of the problem is the following:

* A sequence of $n$ non-negative real numbers $\alpha\_1, \ldots, \alpha\_n$. Here $n$ is a positive natural number. If it makes any difference, I would also be fine with the assumptions that the $\alpha$'s are integers instead of reals.
* A non-negative real number $\beta$. (Again, this number could be integer if it makes any difference.)
* An integer number $d$ such that $1 \leq d < n$.
* An integer number $t$ such that $1 \leq t \leq n$.

The problem asks whether there is a subsequence of $(\alpha \_1, \ldots, \alpha\_n)$ of length at most $t$ such that:

1. The sum of the elements in the subsequence is at least $\beta$. I.e., if the subsequence is $\alpha\_{i\_1}, \ldots, \alpha\_{i\_t}$, then $\sum\_{j=1}^t \alpha\_{i\_j} \geq \beta$.
2. There is no gap larger than $d$ in the subsequence. For example, if a number $\alpha\_i$ is in the subsequence, it cannot happen than none of the numbers $\alpha\_{i-d}, \ldots, \alpha\_{i-1}, \alpha\_{i+1}, \ldots, \alpha\_{i+d}$ are in the sub-sequence. In other words, if two numbers $\alpha\_i$, $\alpha\_j$ are in the subsequence and $j > i + d$, then there must be at least another number in the subsequence among $\alpha\_{i+1}, \ldots, \alpha\_{j-1}$.

I spent quite some time on it, but I could not come up with any reduction from NP-complete problems I am familiar with.
At the same time, I do not have a polynomial-time algorithm for it.
The best I have is a pseudopolinomial-time dynamic programming algorithm which runs in $O(n \beta)$ (when $\beta$ is integer).

**Tags:** np-hardness, np-complete

> **Comments:**
> **username_1**: Have you looked at longest increasing subsequence and similar problems?  The dynamic programming ideas from there might be adaptable.  For instance, if you define $M(i, k)$ as the maximum sum achievable in $\alpha_1, \ldots \alpha_i$ with the restriction that $\alpha_i$ is the $k$-th number in the subsequence, then maybe you can calculate $M(i, k)$ in terms of $M(i - 1, k - 1), \ldots, M(i - d, k - 1)$.  
> **username_2**: Your two versions of condition 2 are not equivalent.  Which one did you intend?  
> **username_3**: Also, the first definition used in condition 2 seems to count a subsequence like $\alpha_1, \alpha_2, \alpha_{n-1}, \alpha_{n}$ as having no gaps > 1 since for each $\alpha$ there is another within distance 1.  

---

## 2 answers

### Answer by username_4 on 2022-12-07. Score: 1

I think this can be solved in PTIME by a rather standard dynamic programming approach.

Define a table $T$ storing, for each prefix length $i$, for each distance $j$, for each sequence length $l$, the maximum weight of a subsequence of the prefix of length $i$ of the input sequence such that the latest selected element is at distance $j$ from the end of the prefix (i.e., letting $x$ the latest selected element, $i-x = j$), and the number of selected elements is $l$. Initialize all cells to $-\infty$.

The table is of polynomial size as it has at most $n^3$ cells.

Now, we can compute the values for $i+1$ from the values for $i$, i.e., for each $i,j,l$, if $j$ is sufficiently small to satisfy condition 2, update $T[i+1,0,l+1]$ to take the max of its current value and of the $i$-th value plus $T[i,j,l]$ (intuitively, we add the leftmost element to the sequence), and update $T[i+1,j+1,l]$ to take the max of its current value and of $T[i,j,l]$ (intuitively, we do not add the leftmost element to the sequence).

This should satisfy the inductive invariant given in the first paragraph, and your desired answer would be the max of $T[n,j,l]$ over all suitable values of $j$ and all $l \leq t$. This algorithm runs in polynomial time.

(I hope this is clear and I didn't misunderstand your problem.)


---

### Answer by username_5 on 2022-12-08. Score: 1

Following the suggestion by username_1, you can build a table with $O(n^2)$ entries.
Entry $M(i,k)$ contains the maximum sum of a valid subsequence of elements $\{\alpha\_1, \ldots, \alpha\_i\}$ of length $k$ and such that the last element of the subsequence is $\alpha\_i$.

Note that, trivially, $M(i, 1) = \alpha\_i$ for all $i \in \{1,\ldots,n\}$.

Also note that if a subsequence of length $k$ ends at $\alpha\_i$, then there must be at least another element among $\{\alpha\_{i-d}, \ldots, \alpha\_{i-1}\}$ in position $k-1$ in the subsequence. Otherwise, the "no gap" condition would be violated.
From this last observation, you can derive the Dynamic Programming recursion:
$$M(i, k) = \max\_{i'=[i-d], \ldots, i-1} \{ M(i', k-1) \} + \alpha\_i$$
where $[i-d] = \max \{ 1, i-d \}$.

Finally, there is a subsequence of length at most $t$ with a sum of at least $\beta$ if:
$$\min \biggl\{ k=1,\ldots,n \; \bigl|\bigr. \; \exists i \in \{k,\ldots,n\} \text{ s.t. } M(i,k) \geq \beta \biggr\} \leq t$$

Interestingly, I stumbled across the same problem very recently, in the context of a special case of the min-Knapsack Problem (in which the $\alpha\_i$ are weights, $\beta$ is the capacity and profits are all unitary).


---

