In the first pass create a difference array of size n-1 where n is the size
of the input array.
D[i] = A[i+1] - A[i]
Look for for the longest consecutive no. of times an element is repeated in
the difference array.
public void longestAP(int[] a, int n) {
int[] diff = new int[n-1];
for(int i = 0; i < n-1; i++) {
diff[i] = a[i+1]-a[i];
}
int maxDiff = diff[0], maxi = 0, maxCount = 1;
int currentDiff = -1, currentCount = 0, currenti = -1;
for(int i = 1; i < n-1; i++) {
if(diff[i] == maxDiff) { maxCount++; }
else {
if(diff[i] == currentDiff) { currentCount++; if (currentCount >
maxCount) { maxDiff = currentDiff; maxCount = currentCount; maxi =
currenti;}}
else {
currentDiff = diff[i]; currenti = i; currentCount = 1;
}
}
}
System.out.print("Elements of the AP: ") ;
for(int i = maxi; i <= maxi+maxCount; i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
On Tue, Feb 5, 2013 at 5:33 PM, Ian Martin Ajzenszmidt <[email protected]
> wrote:
>
>
> On Friday, 8 July 2011 04:13:38 UTC+10, Piyush Sinha 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.
>>
> Click on the following links or copy and paste them into your browser.
> Many interesting possibilities.
>
> https://www.google.com.au/search?client=ubuntu&channel=fs&q=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that+A[i1&ie=utf-8&oe=utf-8&redir_esc=&ei=GpQRUZXnJKaeiAen7oDYAw
>
>
> http://scholar.google.com/scholar?hl=en&q=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that++A[i1]%2C+A[i2]%2C+%E2%80%A6%2C+A[ik]+forms+an+arithmetic+progression%2C+and+k+is+the+largest+possible.&btnG=&as_sdt=1%2C5&as_sdtp=
>
>> --
>> *Piyush Sinha*
>> *IIIT, Allahabad*
>> *+91-8792136657*
>> *+91-7483122727*
>> *https://www.facebook.com/**profile.php?id=100000655377926<https://www.facebook.com/profile.php?id=100000655377926>*
>>
>> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
Vandana Bachani
Graduate Student, MSCE
Computer Science & Engineering Department
Texas A&M University, College Station
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
