wu :: forums « wu :: forums - Longest Accelerating Subsequence » Welcome, Guest. Please Login or Register. Nov 29th, 2024, 1:41am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: ThudnBlunder, Icarus, SMQ, Grimbal, towr, william wu, Eigenray)    Longest Accelerating Subsequence « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Longest Accelerating Subsequence  (Read 5947 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: 7527 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: 7527 Re: Longest Accelerating Subsequence   « Reply #6 on: Dec 29th, 2011, 4:38am » Quote Modify Hm... yes, I think so  . IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board