# Tag Info

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 ...
• 39k
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 ...
• 159k
Accepted

• 277k
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 ...
• 159k
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 ...
• 277k
Accepted

• 7,455

### 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 ...
• 131

### 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 ...
• 39k

• 8,248
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 ...
• 36
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,...
• 159k
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 ...
• 7,455
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 ...
• 277k
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.
• 30.6k

### longest sub-sequence in both directions

One option is to reduce your problem to Longest Common Subsequence. I'll let you figure out how.
• 277k

### Time complexity of finding subsequences of a string segmented into parts

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