array a[] stores numbers
for(i=1;i<n;i++)
{
diff[i-1]=a[i]-a[i-1];
}
maxcount=1;
tempcount=1;
for(j=1;j<n-1;j++)
{
if(diff[j]==diff[j-1])
tempcount++;
else
{
if(tempcount>maxcount)
maxcount=tempcount;
tempcount=1;
}
}
On Sat, Jul 9, 2011 at 11:22 PM, Navneet Gupta <[email protected]>wrote:
> Sorry typo below
>
> On Sun, Jul 10, 2011 at 12:49 PM, Navneet Gupta <[email protected]>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 <[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
>>
>>
>
>
>
> --
> 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.
>
--
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.
