wu :: forums - Print Page


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

        riddles >> cs >> Largest AP subsequence
        
(Message started by: Jigsaw on Jun 24^th, 2008, 7:56am)

Title: Largest AP subsequence
Post by Jigsaw on Jun 24^th, 2008, 7:56am

You're given an array of n elements. Your task is to find a largest subsequence of the array, the elements of which are in Arithmetic Progression.
I've come up with an obvious O(n*n*d) time, O(n) space DP method, where d is the value max-min.
[hide]laps[i][diff]=max_{(j=1 to i-1)}(laps[j][diff]+1)[/hide]

This question came to my mind while going through this problem (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1193022724)(the value of d in the AP found will give the required "i" in that problem).
Is there a method with a better time complexity?

Title: Re: Largest AP subsequence
Post by Jigsaw on Jun 24^th, 2008, 9:58pm

Any idea anyone?
Anyhow one improvement I've thought of is: If d>>n*n, Find out all the nC2 possible differences and search for APs with only these values as differences. It would still be O(n^4) time.

Title: Re: Largest AP subsequence
Post by towr on Jun 25^th, 2008, 1:16am

I suppose I'd start with sorting the array. O(n log n)
Finding all differences sounds like a good idea; and I'll sort those too. O(n² log n)
Then I'll calculate for each difference the modulo of the array, and sort the numbers on the modulo (because only numbers with the same modulo can go together) O(n² * n log n)
And find the longest continuous arithmetic progression in each modulo black O(n * n)

So, O(n³ log n) overall?
Actually, it should be much less, because if we have n² distinct differences, then we already know at most two numbers are in arithmetic progression; because we need the same differences.

Come to think of it, we might be better off using that knowledge more fully.
Hmm, build graphs from the pairs of numbers (edges) with the same distance, and find the longest 'string' amongst them. That almost sounds too simple doesn't it. Should be O(n²).

Title: Re: Largest AP subsequence
Post by cuckoo on Jun 25^th, 2008, 1:56am

O(n^3) is enough.
Assume the array is sorted.
for each pair (i, j), i<j, if a[i] a[j] are the first two elements in the arithmetic progression, then the progression is determined: x[0]=a[i], x[k]=x[0]+k*(a[j]-a[i]). So we can check how many elments of a[j+1..n] are in the progression in O(n) time.

on 06/24/08 at 21:58:59, Jigsaw wrote: