Author |
Topic: Longest Accelerating Subsequence (Read 5851 times) |
|
bazinga
Junior Member
Gender: 
Posts: 53
|
 |
Longest Accelerating Subsequence
« on: May 6th, 2011, 6:30am » |
 Quote  Modify
|
Call a sequence X[1 .. n] of integers accelerating if 2 · X[i] < X[i - 1] + X[i + 1] for all i.
Describe and analyze an efficient algorithm to compute the function lxs(X), which gives
the length of the longest accelerating subsequence of an arbitrary array X of integer
|
|
 IP Logged |
|
|
|
sunny816.iitr
Newbie
Gender:
Posts: 2
|
|
Re: Longest Accelerating Subsequence
« Reply #1 on: Jun 9th, 2011, 10:18am » |
Quote Modify
|
this can be rewritten as x[i+1]-x[i] > x[i]-x[i-1]
create a new difference array and problem reduces to find the longest increasing subsequence, isn't it ?
|
| « Last Edit: Jun 9th, 2011, 11:14am by sunny816.iitr » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Longest Accelerating Subsequence
« Reply #2 on: Jun 9th, 2011, 11:11am » |
Quote Modify
|
That would work if we were looking for a (continuous) subarray, but we're looking for a subsequence, so the elements aren't necessarily consecutive.
For example take input [1,2,3,4]: the longest accelerating subsequence is [1,2,4], but the longest increasing subsequence in the difference array ([1,1,1]) would give [1,2], because the difference array is not increasing.
|
| « Last Edit: Jun 9th, 2011, 11:12am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Longest Accelerating Subsequence
« Reply #3 on: Jun 10th, 2011, 12:58am » |
Quote Modify
|
One obvious O(n2) O(n3) method is to compute for i<j:
mi,j = length of longest accelerating sequence in [X1,...,Xj] ending with ...,Xi,Xj.
You compute it as
mi,j = max k<i, X[i]-X[k]<X[j]-X[i] (mk,i + 1)
mi,j = 2 if no k satisfies the condition.
While computing mi,j, remember ki,j = the value of k that realizes the maximum. Or 0 for the second case.
Also, remember i, j that has the largest mi,j overall.
From there, you can reconstruct the best accelerating array.
The thing to investigate is to compute only "interesting" values of mi,j.
|
| « Last Edit: Dec 29th, 2011, 4:39am by Grimbal » |
IP Logged |
|
|
|
MrLambert
Newbie
Posts: 13
|
|
Re: Longest Accelerating Subsequence
« Reply #4 on: Oct 31st, 2011, 8:53am » |
Quote Modify
|
nice approach.
|
|
IP Logged |
|
|
|
krishnav
Newbie
Posts: 12
|
|
Re: Longest Accelerating Subsequence
« Reply #5 on: Dec 28th, 2011, 9:49pm » |
Quote Modify
|
@Grimbal: isn't it O(n3) ?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Longest Accelerating Subsequence
« Reply #6 on: Dec 29th, 2011, 4:38am » |
Quote Modify
|
Hm... yes, I think so  .
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print