The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
1answer
94 views

Maximum sum subset of an array with an extra condition

We are given numbers $n \leq 200$, $k \leq 10$ and an array of $3n$ positive integers not greater than $10^6$. Find the maximum possible sum of a subset of elements of this array, such that in every ...
1
vote
1answer
37 views

Algorithm to merge two incomplete lists of symbols (strings) into a complete one

I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution. Let's say we have two ordered lists of symbols (strings): ...
5
votes
0answers
106 views

Longest Repeated (Scattered) Subsequence in a String

Informal Problem Statement: Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right ...
5
votes
0answers
153 views

Subarray whose (sum × length) is maximum

Consider the following problem: Given an array of $n$ integer numbers (positive and negative), find a (contiguous) subarray for which the product $(\text{sum of the elements})\times(\text{length ...
2
votes
2answers
1k views

Detecting a subsequence that's an arithmetic progression, in a sorted sequence

I have following problem: I have a sorted sequence of $N$ integers (assume they are monotonically increasing). I want to check whether there is any subsequence of length $\ge N/4$, such that ...
2
votes
1answer
257 views

Given an array of N integers, how can you find M elements to remove so that the array will end up in sorted order?

Here is my approach First I compute the longest non decreasing sub-sequence in $N \log N$ time. Algorithm to do this (that only uses arrays and binary search) can be found here: ...
4
votes
1answer
351 views

Finding the subset of $S$ that sums up to $k$ using a black box in $O(n)$ time

Suppose you are given an input set $S$ of $n$ numbers, and a black box that if given any sequence of real numbers and an integer $k$ instantly and correctly answers whether there is a subset of input ...
4
votes
2answers
109 views

Longest subsequence such that A[i].x < A[i+1].y

I have an issue for which I am looking for an algorithm (if it exists) What I have: An array of items which have certain properties, e.g. item $A$ has properties $x$ and $y$. Example: $[ A(x,y), ...
4
votes
1answer
156 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
339 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
1k 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
105 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
2k 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
48 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
276 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 ...
7
votes
4answers
4k 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 ...
17
votes
3answers
802 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
428 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 ...
7
votes
1answer
142 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
805 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 ...