Try this 1. Find the min and max in O(n) time. 2. For A.P. = mix to max/N , we find max possible subsequence.
For example 1,2,3,0,4,7,19,6,8,10,24.....(could be more but trying to show the approach) We see min = 1 and max = 8 hence we need to try for diff = 1 to 8/size(arr) In this case, we will find that for diff = 2, we are able to find a sequence 2,4,6,8,10 of length 5. Hence max is this sequence (Only store the first value of every sequence and make some variable diffForMaxSequence to store diff value 2 here) Complexity will depend upon the range of numbers but we can look for optimization to not go till diff = max/N On Fri, Jul 8, 2011 at 3:18 PM, sunny agrawal <[email protected]>wrote: > Here is one Brute Force solution O(n^3) > > for each i and j in array(j > i) {where a[i] is first term of AP and a[j] > is second term} > compute d = a[j]-a[i] > and now from j+1 to end of the array search for a+2d,a+3d,a+4d > ................ > and keep track of longest :) > > > On Fri, Jul 8, 2011 at 1:28 AM, Piyush Sinha <[email protected]>wrote: > >> Nopes....its about finding subsequence.... >> >> On 7/8/11, rajeev bharshetty <[email protected]> wrote: >> > Should the sequence beContinuos ??? >> > >> > On Fri, Jul 8, 2011 at 1:18 AM, sunny agrawal >> > <[email protected]>wrote: >> > >> >> @rajiv >> >> if Count = 2 means 3 elements isn't it a,a+d,a+2d >> >> else according to you >> >> for case 10 12 14 24 26 28 >> >> diff 2 2 10 2 2 >> >> diff 2 has count 4 so will you say ap of 4 elements with diff 2 >> >> >> >> On Fri, Jul 8, 2011 at 1:06 AM, rajeev bharshetty >> >> <[email protected]>wrote: >> >> >> >>> @sunny Keep count of longest repeated element in diff i.e 2 so count >> =2 >> >>> so >> >>> ap of 2 elem with diff 2 . >> >>> >> >>> On Fri, Jul 8, 2011 at 1:03 AM, sunny agrawal >> >>> <[email protected]>wrote: >> >>> >> >>>> @rajiv >> >>>> Fails i think >> >>>> think for 10 12 24 26 >> >>>> diff is 2 12 2 >> >>>> so do you want to say there is an AP pf 3 elements with d = 2, i >> can't >> >>>> see any :P >> >>>> your solution fails because there can be many APs in the array with >> the >> >>>> same value of d and you will finish up by combining all those APs >> >>>> >> >>>> >> >>>> On Fri, Jul 8, 2011 at 12:55 AM, rajeev bharshetty < >> [email protected] >> >>>> > wrote: >> >>>> >> >>>>> >> >>>>> Check the differences between the adjacent elements and store the >> >>>>> differenecs in diff[i] array >> >>>>> then scan through the array . >> >>>>> then keep a count for all the repeated diff elements ,the sequence >> of >> >>>>> indexes with max count is the solution . >> >>>>> >> >>>>> >> >>>>> >> >>>>> >> >>>>> On Thu, Jul 7, 2011 at 11:43 PM, Piyush Sinha < >> [email protected] >> >>>>> > wrote: >> >>>>> >> >>>>>> Given an array of integers A, give an algorithm to find the longest >> >>>>>> Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, >> >>>>>> such that >> >>>>>> >> >>>>>> A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is >> the >> >>>>>> largest possible. >> >>>>>> >> >>>>>> The sequence S1, S2, …, Sk is called an arithmetic progression if >> >>>>>> >> >>>>>> Sj+1 – Sj is a constant. >> >>>>>> >> >>>>>> -- >> >>>>>> *Piyush Sinha* >> >>>>>> *IIIT, Allahabad* >> >>>>>> *+91-8792136657* >> >>>>>> *+91-7483122727* >> >>>>>> *https://www.facebook.com/profile.php?id=100000655377926 * >> >>>>>> >> >>>>>> -- >> >>>>>> You received this message because you are subscribed to the Google >> >>>>>> Groups "Algorithm Geeks" group. >> >>>>>> To post to this group, send email to [email protected]. >> >>>>>> To unsubscribe from this group, send email to >> >>>>>> [email protected]. >> >>>>>> For more options, visit this group at >> >>>>>> http://groups.google.com/group/algogeeks?hl=en. >> >>>>>> >> >>>>>> >> >>>>> -- >> >>>>> You received this message because you are subscribed to the Google >> >>>>> Groups "Algorithm Geeks" group. >> >>>>> To post to this group, send email to [email protected]. >> >>>>> To unsubscribe from this group, send email to >> >>>>> [email protected]. >> >>>>> For more options, visit this group at >> >>>>> http://groups.google.com/group/algogeeks?hl=en. >> >>>>> >> >>>> >> >>>> >> >>>> >> >>>> -- >> >>>> Sunny Aggrawal >> >>>> B-Tech IV year,CSI >> >>>> Indian Institute Of Technology,Roorkee >> >>>> >> >>>> -- >> >>>> You received this message because you are subscribed to the Google >> >>>> Groups >> >>>> "Algorithm Geeks" group. >> >>>> To post to this group, send email to [email protected]. >> >>>> To unsubscribe from this group, send email to >> >>>> [email protected]. >> >>>> For more options, visit this group at >> >>>> http://groups.google.com/group/algogeeks?hl=en. >> >>>> >> >>> >> >>> -- >> >>> You received this message because you are subscribed to the Google >> Groups >> >>> "Algorithm Geeks" group. >> >>> To post to this group, send email to [email protected]. >> >>> To unsubscribe from this group, send email to >> >>> [email protected]. >> >>> For more options, visit this group at >> >>> http://groups.google.com/group/algogeeks?hl=en. >> >>> >> >> >> >> >> >> >> >> -- >> >> Sunny Aggrawal >> >> B-Tech IV year,CSI >> >> Indian Institute Of Technology,Roorkee >> >> >> >> -- >> >> You received this message because you are subscribed to the Google >> Groups >> >> "Algorithm Geeks" group. >> >> To post to this group, send email to [email protected]. >> >> To unsubscribe from this group, send email to >> >> [email protected]. >> >> For more options, visit this group at >> >> http://groups.google.com/group/algogeeks?hl=en. >> >> >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups >> > "Algorithm Geeks" group. >> > To post to this group, send email to [email protected]. >> > To unsubscribe from this group, send email to >> > [email protected]. >> > For more options, visit this group at >> > http://groups.google.com/group/algogeeks?hl=en. >> > >> > >> >> >> -- >> *Piyush Sinha* >> *IIIT, Allahabad* >> *+91-8792136657* >> *+91-7483122727* >> *https://www.facebook.com/profile.php?id=100000655377926 * >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Sunny Aggrawal > B-Tech IV year,CSI > Indian Institute Of Technology,Roorkee > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards, Navneet -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
