Author |
Topic: Largest AP subsequence (Read 2826 times) |
|
Jigsaw
Guest
|
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.
laps[i][diff]=max(j=1 to i-1)(laps[j][diff]+1)
This question came to my mind while going through this problem(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?
|
| « Last Edit: Jun 24th, 2008, 9:59pm by jagatsastry » |
 IP Logged |
|
|
|
Jigsaw
Guest
|
 |
Re: Largest AP subsequence
« Reply #1 on: Jun 24th, 2008, 9:58pm » |
 Quote  Modify
 Remove
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Largest AP subsequence
« Reply #2 on: Jun 25th, 2008, 1:16am » |
Quote Modify
|
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(n2 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(n2 * n log n)
And find the longest continuous arithmetic progression in each modulo black O(n * n)
So, O(n3 log n) overall?
Actually, it should be much less, because if we have n2 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(n2).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
cuckoo
Junior Member
Gender:
Posts: 57
|
|
Re: Largest AP subsequence
« Reply #3 on: Jun 25th, 2008, 1:56am » |
Quote Modify
|
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 Jun 24th, 2008, 9:58pm, Jigsaw wrote: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. |
|
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print