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

  • 4
    $\begingroup$ 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)$. $\endgroup$ Commented Dec 4, 2022 at 16:33
  • 3
    $\begingroup$ Your two versions of condition 2 are not equivalent. Which one did you intend? $\endgroup$
    – D.W.
    Commented Dec 5, 2022 at 3:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – mhum
    Commented Dec 6, 2022 at 22:52

2 Answers 2


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


Following the suggestion by Manuel Lafond, 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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