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
Sorry typo below
On Sun, Jul 10, 2011 at 12:49 PM, Navneet Gupta navneetn...@gmail.comwrote:
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
array a[] stores numbers
for(i=1;in;i++)
{
diff[i-1]=a[i]-a[i-1];
}
maxcount=1;
tempcount=1;
for(j=1;jn-1;j++)
{
if(diff[j]==diff[j-1])
tempcount++;
else
{
if(tempcountmaxcount)
maxcount=tempcount;
tempcount=1;
}
}
On Sat, Jul 9, 2011
@yogesh- can u explain with an example pls?
--
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.
Can think of a O(n^2) solution
On Sun, Jul 10, 2011 at 6:53 PM, raj singh ankurkaku...@gmail.com wrote:
@yogesh- can u explain with an example pls?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
@raj :
array a[]= 2,3,5,6,7,8,10,12
diff[]= 1,2,1,1,1,2,2
maxcount=tempcount=1 // because am not takin in consideration of 0th index
value of diff[]
now in for loop
for j=1
check diff[j]==diff[j-1] //not equal
so check tempcountmaxcount or not //its also not
so maxcount remains same
i thinks mine is just O(n)
On Sun, Jul 10, 2011 at 5:31 AM, Yogesh Yadav medu...@gmail.com wrote:
@raj :
array a[]= 2,3,5,6,7,8,10,12
diff[]= 1,2,1,1,1,2,2
maxcount=tempcount=1 // because am not takin in consideration of 0th
index value of diff[]
now in for loop
for j=1
check
@Yogesh
your solution will give maximum Contiguous AP only
it will fail for the array A[] = {1,2,3,4,5,6,8,10,12,14}
your algo will give output that there is an Longest AP of 6 elements which
is wrong
checkout this http://theory.cs.uiuc.edu/%7Ejeffe/pubs/pdf/arith.pdf for an
O(n^2) algorithm
On
@sunny: my algo will give 5 as answer and i guess its right... if am
wrong plz explain where and why my logic is wrong
On Sun, Jul 10, 2011 at 5:37 AM, sunny agrawal sunny816.i...@gmail.comwrote:
@Yogesh
your solution will give maximum Contiguous AP only
it will fail for the array A[] =
@sunny: my algo will give 5 as answer and i guess its right... if am
wrong plz explain where and why my logic is wrong
On Sun, Jul 10, 2011 at 5:37 AM, sunny agrawal sunny816.i...@gmail.comwrote:
@Yogesh
your solution will give maximum Contiguous AP only
it will fail for the array A[] =
@sunny: my algo will give 6 as answer and i guess its right... if am
wrong plz explain where and why my logic is wrong
On Sun, Jul 10, 2011 at 5:37 AM, sunny agrawal sunny816.i...@gmail.comwrote:
@Yogesh
your solution will give maximum Contiguous AP only
it will fail for the array A[] =
Longest AP for that Example is of 7 elements
2,4,6,8,10,12,14
now see your mistake ...
as i have already told you that u r looking for only contiguous AP's and
that won't work
On Sun, Jul 10, 2011 at 7:18 PM, Yogesh Yadav medu...@gmail.com wrote:
@sunny: my algo will give 6 as
@sunny : thanks ..i got it...
On Sun, Jul 10, 2011 at 5:55 AM, sunny agrawal sunny816.i...@gmail.comwrote:
Longest AP for that Example is of 7 elements
2,4,6,8,10,12,14
now see your mistake ...
as i have already told you that u r looking for only contiguous AP's and
that won't
yeah then it will be possible in O(n^2)
On Sun, Jul 10, 2011 at 5:57 AM, Yogesh Yadav medu...@gmail.com wrote:
@sunny : thanks ..i got it...
On Sun, Jul 10, 2011 at 5:55 AM, sunny agrawal sunny816.i...@gmail.comwrote:
Longest AP for that Example is of 7 elements
2,4,6,8,10,12,14
try Matrix search...
On Sun, Jul 10, 2011 at 7:34 PM, Yogesh Yadav medu...@gmail.com wrote:
yeah then it will be possible in O(n^2)
On Sun, Jul 10, 2011 at 5:57 AM, Yogesh Yadav medu...@gmail.com wrote:
@sunny : thanks ..i got it...
On Sun, Jul 10, 2011 at 5:55 AM, sunny agrawal
Step 1: first make a diff[][]
Step 2: search the diff in matrix
Complexity will be O(n^2)
On Sun, Jul 10, 2011 at 6:24 AM, JAIDEV YADAV jaid...@gmail.com wrote:
try Matrix search...
On Sun, Jul 10, 2011 at 7:34 PM, Yogesh Yadav medu...@gmail.com wrote:
yeah then it will be possible in
@Sunny: Can you please explain that paper in simple english please?? Thoda
zyaada complex ho gaya hai.
O(N^3) DP is simple and understandable.
--
DK
http://twitter.com/divyekapoor
http://www.divye.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
Never mind. Figured it out, though in possibly different from the paper.
Principle of optimality to the rescue! :)
O(n^2)
DP equations:
LAP[i, j] = Longest AP in range [i,j] of the sequence
LAP[0, j] = max{LAP[0, k] (for all k in range [0, j-1]) extended with a[j],1
(the element a[j] itself)}
@Divye Sir
I just came to know this is not a general Algorithm
This works only for sorted Array
this is Some description about the algo in paper
this algo uses the property of a AP that for every 3 consecutive elements of
an AP(a1,a2,a3)
a1+a3 = 2*a2
*L[i j] stores the maximum length of an
@Sunny: We don't need ever to calculate generic L[i,j] as we can do this
problem by simply calculating L[0,j] which reduces the dimensionality of the
problem. Here's a modified solution on the same lines as the one originally
proposed. Version 2 uses hash table. Complexity is O(N^2) (if hash
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,
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
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
@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,
@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.comwrote:
@sunny Keep count of
Should the sequence beContinuos ???
On Fri, Jul 8, 2011 at 1:18 AM, sunny agrawal sunny816.i...@gmail.comwrote:
@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
Nopesits 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.comwrote:
@rajiv
if Count = 2 means 3 elements isn't it a,a+d,a+2d
else according to
27 matches
Mail list logo
