Sorry typo below
On Sun, Jul 10, 2011 at 12:49 PM, Navneet Gupta <navneetn...@gmail.com>wrote:
> 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 = 24 hence we need to try for diff = 1 to 24
> /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 <sunny816.i...@gmail.com>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 <ecstasy.piy...@gmail.com>wrote:
>>
>>> Nopes....its about finding subsequence....
>>>
>>> On 7/8/11, rajeev bharshetty <rajeevr...@gmail.com> wrote:
>>> > Should the sequence beContinuos ???
>>> >
>>> > On Fri, Jul 8, 2011 at 1:18 AM, sunny agrawal
>>> > <sunny816.i...@gmail.com>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
>>> >> <rajeevr...@gmail.com>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
>>> >>> <sunny816.i...@gmail.com>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 <
>>> rajeevr...@gmail.com
>>> >>>> > 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 <
>>> ecstasy.piy...@gmail.com
>>> >>>>> > 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 algogeeks@googlegroups.com.
>>> >>>>>> To unsubscribe from this group, send email to
>>> >>>>>> algogeeks+unsubscr...@googlegroups.com.
>>> >>>>>> 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 algogeeks@googlegroups.com.
>>> >>>>> To unsubscribe from this group, send email to
>>> >>>>> algogeeks+unsubscr...@googlegroups.com.
>>> >>>>> 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 algogeeks@googlegroups.com.
>>> >>>> To unsubscribe from this group, send email to
>>> >>>> algogeeks+unsubscr...@googlegroups.com.
>>> >>>> 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 algogeeks@googlegroups.com.
>>> >>> To unsubscribe from this group, send email to
>>> >>> algogeeks+unsubscr...@googlegroups.com.
>>> >>> 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 algogeeks@googlegroups.com.
>>> >> To unsubscribe from this group, send email to
>>> >> algogeeks+unsubscr...@googlegroups.com.
>>> >> 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 algogeeks@googlegroups.com.
>>> > To unsubscribe from this group, send email to
>>> > algogeeks+unsubscr...@googlegroups.com.
>>> > 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 algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Regards,
> Navneet
>
>
--
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
