7 votes
Accepted

Existence / non-existence of a sequence with short longest increasing subsequence and decreasing subsequence?

The answer to the OP's question is, no if $N\le 7$ and yes otherwise. For given any positive integer $r$ and $s$, the celebrated Erdős–Szekeres theorem shows that for any sequence of distinct real ...
John L.'s user avatar
  • 39k
6 votes
Accepted

Returning random integer from interval based on last result and a seed

I suggest you pick a random permutation on the range $[a,b]$, i.e., a bijective function $\pi:[a,b]\to [a,b]$. Then, maintain a counter $i$ that starts at $i=a$; at each step, output $\pi(i)$ and ...
D.W.'s user avatar
  • 159k
6 votes
Accepted

Shortest subsequence containing all elements

Start by computing the set of all elements in the input sequence. This takes time $O(n\log n)$ if we are only allowed comparisons, and $O(n)$ using a hash table. Suppose there are $m$ such elements $...
Yuval Filmus's user avatar
5 votes
Accepted

Longest Repeated (Scattered) Subsequence in a String

The special case of $k = n/2$ is the same problem as this CST.SE question How hard is unshuffling a string? asks. Buss and Soltys proved NP-completeness of this problem [1] by reducing 3-Partition ...
pcpthm's user avatar
  • 2,348
4 votes

Find longest subsequence in array with given condition

In the following answer, I show how to solve in $O(n\log n)$ the following similar question: Given an array $A$ and a number $k$, find the longest contiguous subsequence in which any two elements $...
Yuval Filmus's user avatar
4 votes
Accepted

How is n-gram different from k-mer?

Yes, they mean the same thing. A n-gram is a sequence of n consecutive things (words, letters, whatever). A k-mer is a sequence of k consecutive things (DNA basepairs). The phrase k-mer is more ...
D.W.'s user avatar
  • 159k
4 votes
Accepted

Number of contiguous subsequences summing to a given target

Here is a simple randomized $O(n)$ time algorithm. We start by rephrasing your problem slightly. Suppose that the original array is $a_1,\ldots,a_n$. Form a new array $b_0,\ldots,b_n$ containing the ...
Yuval Filmus's user avatar
4 votes
Accepted

Maximum product of contiguous subsequence over $\mathbb{R}$

You can adopt the dynamic programming solution; the other solution looks harder to adapt. Given an array $A_1,\ldots,A_n$, we let $P_i$ be the maximum positive product of a subsequence of $A_1,\ldots,...
Yuval Filmus's user avatar
4 votes
Accepted

Given a list of strings, find every pair $(x,y)$ where $x$ is a subsequence of $y$. Possible to do better than $O(n^2)$?

No, it is not possible to do better unless the Strong Exponential Time Hypothesis (SETH) fails. If we could solve this problem substantially faster than $O(n^2)$ we would immediately obtain a much ...
Tom van der Zanden's user avatar
3 votes
Accepted

How can I efficiently generate the shortest list of arguments for the range() function that will generate a given list of integers?

I'm assuming the input does not have duplicates, e.g. not [1, 2, 2, 5]. No, an efficient (polynomial time) algorithm does not exist to our best knowledge, as per "...
orlp's user avatar
  • 13.4k
3 votes
Accepted

Complexity of Longest Palindromic Subsequence Algorithm

The dynamic programming approach is indeed O(n^2). However, the recursive solution is exponential in n: any time two characters ...
Gassa's user avatar
  • 831
3 votes
Accepted

Shortest Non-Subsequence String With Constant-Size Alphabet

For each $i$, let $s(i)$ be a string of length $f(i)+1$ that is not a subsequence of $S[1\ldots i]$, then what you seek for is exactly $s(n)$. Also denote $g(i) = \min\left(\ell\left(i,\sigma_1\right),...
xskxzr's user avatar
  • 7,455
3 votes

Proof that the length of the largest ascending subsequence is the number of decreasing subsequences

You should read up on Patience Sorting first; that's a greedy algorithm to calculate a partition into nonincreasing subsequences (described there as piles of cards). Moreover, the number of ...
Maks Verver's user avatar
3 votes

How can I efficiently find the largest positive interval in an unsorted array?

Hint, scan the array from left to right, keeping track of the smallest number so far and using that number to compute the largest interval whose right endpoint is the number just scanned. Here is the ...
John L.'s user avatar
  • 39k
3 votes

Use dynamic programming to merge two arrays such that the number of repetitions of the same element is minimised

Here is an algorithm that computes the minimum cost that is about as simple as possible and as fast as possible. Count the total number of each character in $m$ and $n$. Let them be $c(a), c(b), \...
John L.'s user avatar
  • 39k
3 votes
Accepted

Test if there exists an integer k to add to one sequence to make it a subsequence of another sequence

Here is a heuristic that won't always work, but should work with high probability if the integers in the arrays are chosen randomly from a large enough space. Initialize a hashtable of counts $C$ to ...
D.W.'s user avatar
  • 159k
3 votes
Accepted

What are the exponential alternatives that are skipped in dynamic programming for longest increasing subsequence?

Go over all $2^n$ subsequences. For each one, check whether it is increasing. There are two meanings of subsequence: contiguous subsequence and arbitrary subsequence. For example, $1,3$ is a non-...
Yuval Filmus's user avatar
3 votes

Matching two noisy / lossy versions of the same data stream to each other

Sequence Alignment is exactly what I was looking for -- thank you @Yuval Filmus! This is commonly used in Genetics to line up genes, etc. Best I can understand, these typically require a fixed ...
Mala's user avatar
  • 141
2 votes

Find longest subsequence in array with given condition

The solution by Daniel Saad is on the right track, but unfortunately isn't complete. It's not difficult to come up with an example when the greedy algorithm fails and hence the item should be better ...
Maxim's user avatar
  • 640
2 votes
Accepted

Why does Banded Needleman-Wunsch give alignments with no more than d base pairs of indels?

You are correct, the number of insertions/deletions $d$ is not constrained (only) by the bandwidth. However, the algorithm only uses the fact that if we know $d$, then the path must stay within the $...
Discrete lizard's user avatar
  • 8,248
2 votes
Accepted

Maximum sum subset of an array with an extra condition

Let's call the length of the array $t \cdot n$, so in your task $t=3$. Since in every fragment $[1, n], [n+1, 2n] \ldots [(t-1)n+1, tn]$ we can't take more than $k$ elements, so the number of taken ...
elvina's user avatar
  • 36
2 votes
Accepted

How to efficiently code Dynamic Time Warping algorithm with a locality constrain?

There is a $O(nmW)$-time algorithm using dynamic programming. Let $A[i,j] = $ the cost of the best matching of $[s_1,\dots,s_i]$ to $[t_1,\dots,t_j]$ such that $s_i$ is matched to $t_j$. Then $$A[i,...
D.W.'s user avatar
  • 159k
2 votes
Accepted

How to check if $m$ numbers in a sequence satisfy a condition, such that all these numbers are spaced apart by at least $k$?

As Yuval Filmus said in the comment, you can solve the optimization version (finding maximum viable $m$, which is a stronger version) by dynamic programming. Let $m_i$ be the maximum viable elements ...
xskxzr's user avatar
  • 7,455
2 votes
Accepted

Number of possible sequence partitioning

The problem formulation is not entirely clear. This answer assumes that the allowed subsequences are of the form $10^*1$. Other variants can be solved in a similar way. Suppose that the original ...
Yuval Filmus's user avatar
2 votes
Accepted

How is the Longest Common Sub-sequence of two sequences is a special case of the Sequence Alignment problem?

The problem of finding a longest common subsequence can be answered by computing the alignment where match is rewarded by +1 while mismatch and insdel penalty are both 0.
Hendrik Jan's user avatar
  • 30.6k
2 votes

longest sub-sequence in both directions

One option is to reduce your problem to Longest Common Subsequence. I'll let you figure out how.
Yuval Filmus's user avatar
2 votes

Time complexity of finding subsequences of a string segmented into parts

Yes, your analysis is correct.
2 votes

Give an efficient dynamic programming algorithm that decides if a string is an interleaving of two other strings

Let's use caps, S for input string, A for x and B for y. Furthermore, let |S| = lenS, |A| = lenA, |B| = lenB. With any Dynamic Programming problem, it is useful to ...
Vemana's user avatar
  • 31
2 votes

Can I find all the common subsequences between 2 sequences by using dynamic programming?

Denote the two strings by $s = s_1,\ldots, s_n$ and $t = t_1,\ldots, t_m$. Let $\mathcal{U}(i,j)$ denote the multiset of common subsequences of $s_1,\ldots,s_i$ and $t_1,\ldots,t_j$ which contain $s_i$...
Yuval Filmus's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible