wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Longest Accelerating Subsequence
        
(Message started by: joshi.prahlad on May 6^th, 2011, 6:30am)

Title: Longest Accelerating Subsequence
Post by joshi.prahlad on May 6^th, 2011, 6:30am

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

Title: Re: Longest Accelerating Subsequence
Post by sunny816.iitr on Jun 9^th, 2011, 10:18am

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 ?

Title: Re: Longest Accelerating Subsequence
Post by towr on Jun 9^th, 2011, 11:11am

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.

Title: Re: Longest Accelerating Subsequence
Post by Grimbal on Jun 10^th, 2011, 12:58am

One obvious ~~O(n²)~~ O(n³) method is to compute for i<j:
m_i,j = length of longest accelerating sequence in [X₁,...,X_j] ending with ...,X_i,X_j.

You compute it as
m_i,j = max _{k<i, X[i]-X[k]<X[j]-X[i]} (m_k,i + 1)
m_i,j = 2 if no k satisfies the condition.

While computing m_i,j, remember k_i,j = the value of k that realizes the maximum. Or 0 for the second case.
Also, remember i, j that has the largest m_i,j overall.

From there, you can reconstruct the best accelerating array.

The thing to investigate is to compute only "interesting" values of m_i,j.

Title: Re: Longest Accelerating Subsequence
Post by MrLambert on Oct 31^st, 2011, 8:53am

nice approach.

Title: Re: Longest Accelerating Subsequence
Post by krishnav on Dec 28^th, 2011, 9:49pm

@Grimbal: isn't it O(n³) ?

Title: Re: Longest Accelerating Subsequence
Post by Grimbal on Dec 29^th, 2011, 4:38am

Hm... yes, I think so :-/.