The subsequences tag has no wiki summary.
4
votes
1answer
66 views
Find the longest subsequence of two strings
I want to know which is the best way to find the longest common subsequence of two strings
0
votes
1answer
212 views
Finding the longest common subsequence algorithm using hash table Slow
I've designed an algorithm to find the longest common subsequence. these are steps:
Starts with i = 0
Picks the first letter from the first string start from ...
5
votes
1answer
296 views
Count unique increasing subsequences of length 3 in $O(n\log n)$
Problem: Given an array of $n$ integers, $A[1 \dots n]$, such that any integer occurs at most 2 times in the array, we have to find the number of unique increasing subsequences of length 3 (duplicate ...
4
votes
1answer
95 views
Improving Time Bound of this Algorithm past $O(n^2)$
I recently came across the following interesting problem - one is given a sequence of Xs and Ys such as ...
5
votes
1answer
233 views
Find the longest repeated pattern in a string
I'm looking for an efficient algorithm to find the longest repeated pattern in a string.
For example, consider the following string of numbers:
...
0
votes
0answers
45 views
Longest range with sum smaller than K [duplicate]
Possible Duplicate:
Dynamic programming table for finding similar substrings is too large
Say I have a sequence $S$ of 0s and 1s such as $S = [1, 0, 0, 1, 0, 1]$
How would I efficiently ...
1
vote
0answers
160 views
Longest Increasing Subsequence
I got no responses on stackoverflow, so I'm asking here:
How useful is the LIS (Longest Increasing Subsequence) problem in tackling other CS problems? There are a few algorithms, using patience ...
6
votes
3answers
1k views
Fastest algorithm for finding the longest palindrome subsequence
First of all we must read a word, and a desired size.
Then we need to find the longest palindrome created by characters in this word used in order.
For example for size = 7 and word = "abcababac" the ...
16
votes
3answers
611 views
How to use a greedy algorithm to find the non-decreasing sequence closest to the given one?
You are given n integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ between $0$ and $l$ with the requirement that the $b_i$'s form a ...
4
votes
3answers
280 views
How to output all longest decreasing sequences
Suppose I have an array of integers having length $N$. How can I output all longest decreasing sequences? (A subsequence consists of elements of the array that do not have to be consecustive, for ...
6
votes
1answer
106 views
Find subsequence of maximal length simultaneously satisfying two ordering constraints
We are given a set $F=\{f_1, f_2, f_3, …, f_N\}$ of $N$ Fruits. Each Fruit has price $P_i$ and vitamin content $V_i$; we associated fruit $f_i$ with the ordered pair $(P_i, V_i)$. Now we have to ...
17
votes
3answers
536 views
Is there an algorithm which finds sorted subsequences of size three in $O(n)$ time?
I want to prove or disprove the existence of an algorithm which, given an array $A$ of integers, finds three indices $i, j$ and $k$ such that $i < j < k$ and $A[i] < A[j] < A[k]$ (or finds ...
