Longest Arithmetic Progression Sequence in Java
The task is to find the length of the largest sequence in an array to form an arithmetic progression. The array arr[] is given. Longest Arithmetic Progression Sequence in Java
Algorithm
- set i1 to j1-1 and k1 to j1+1 at initialization
- While i1 >= 0 and k1 = number-1, carry out the following.
- We are done if set[i] + set[k] equals 2*set[j].
- Decrement I if set[i] + set[k] > 2*set[j] (do I–).
- If set[i] + set[k] is not equal to 2*set[j], then raise k (do k++).
Input : int arr = {20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130};
Output: 12
Explanation: The arithmetic progression sequence is formed by the numbers 20 , 30 , 40 , 50, 60 , 70 , 80 , 90 , 100 , 110 , 120 , and 130 where the common difference is 10, and the total number of numbers in the sequence is 12.
Example2
Input: int arr[] = {5 , 7 , 10 , 9 , 14 , 15 , 20 , 25 , 90 , 100 , 30 , 40 } ;
Output: 6
Explanation: The arithmetic progression sequence comprises the numbers 5 , 1 , 15 , 20, 25, and 30, with a common difference of 5 and a total of 6 numbers in the sequence.
Naive Approach
Assuming that the first two elements of the arithmetic progression are a1 and a2, the naive or straightforward approach is to consider each pair one at a time. The first two components allow us to determine a common difference. Using this common difference, we may determine the remaining components of the arithmetic progression. We can keep track of the total number of elements for that arithmetic progression while determining the succeeding elements. For each pair, we will determine this count, then compare the results to see which has the longest arithmetic sequence. Take note of the program program Program for the longest arithmetic progression using the Naive Approach
LongestArithmeticProgression1.java
public class LongestArithmeticProgression1
{
public int find_max_no ( int i1 , int j1 )
{
int max_no ;
return max_no = ( i1 > j1 ) ? i1 : j1 ;
}
public int find_longest_ap_seq ( int arr1 [ ] , int size1 )
{
if ( size1 < = 2 )
{
return size1 ;
}
int answer = -1 ;
for (int i1 = 0 ; i1 < size1 – 2 ; i1++ )
{
for ( int j1 = i1 + 1 ; j1 < size1 – 1 ; j1++ )
{
int commondiff = arr1 [ j1 ] - arr1 [ i1 ] ;
int m = 2 ;
int ce = 2 ;
for(int k1 = j1 + 1 ; k1 < size1 ; k1++ )
{
if ( ( arr1[ i1 ] + m * commondiff ) == arr1 [ k1 ] )
{
ce = ce + 1 ;
m = m + 1 ;
}
}
answer = find_max_no ( answer , ce ) ;
}
}
return answer ;
}
public static void main ( String argvs [ ] )
{
LongestArithmeticProgression1 obj1 = new LongestArithmeticProgression1();
int arr1 [ ] = {20 , 30 , 40 , 50 , 60 , 70 , 80 , 90 , 100 , 110 , 120 , 130 } ;
int size1 = arr1 . length ;
int longest_seq = obj1 . find_longest_ap_seq ( arr1 , size1 ) ;
System . out . println ( " For the following array: " ) ;
for ( int k1 = 0 ; k1 < size1 ; k1++ )
{
System . out . print ( arr1[ k1] + " " ) ;
}
System . out . println ( " \n " ) ;
System . out . println ( " The length of the longest arithmetic progression sequence is: " + longest_seq ) ;
int arr2 [ ] = {5 , 7 , 10 , 9 , 14 , 15 , 20 , 25 , 90 , 100 , 30 , 40 } ;
size1 = arr2 . length ;
longest_seq = obj1 . find_longest_ap_seq (arr2 , size1 ) ;
System . out . println (" \n " ) ;
System . out . println ( " For the following array : " ) ;
for( int k1 = 0 ; k1 < size1; k1++)
{
System . out . print ( arr2 [ k1 ] + " " ) ;
}
System . out . println (" \n ") ;
System . out . println ( " The length of the longest arithmetic progression sequence is: " + longest_seq ) ;
}
}
Output
Complexity analysis: The program in question has three for-loops that are nestable. As a result, the preceding program has an O(n3) time complexity, where n is the total number of entries in the input array. The program above’s constant spatial complexity, or O (1).
It is necessary to use several optimization techniques to lower the program's excessively high O(n3) time complexity. The next method demonstrates the same.
Dynamic Programming Approach
Java Program for longest arithmetic progression using Dynamic Programming Approach
LongestArithmeticProgression2.java
import java.util.HashMap ;
public class LongestArithmeticProgression2
{
public int find_max_no ( int i1 , int j1 )
{
int max_no ;
return max_no = ( i1 > j1 ) ? i1 : j1 ;
}
public int find_longest_ap_seq ( int arr1 [ ] , int size1)
{
if( size1 <= 2 )
{
return size1 ;
}
int dp1 [ ] [ ] = new int [ size1 ] [ size1 ] ;
HashMap < Integer , Integer > hm1 = new HashMap < Integer , Integer > ( ) ;
int answer = 0 ;
for ( int i1 = 0 ; i1 < size1 ; i1++ )
{
for ( int j1 = i1 + 1 ; j1 < size1 ; j1++ )
{
dp1 [ i1 ][ j1 ] = 2 ;
int r = 2 * arr1 [ i1 ] - arr1 [ j1 ] ;
if ( hm1 . containsKey ( r ) )
{
int q = hm1 . get ( r ) ;
dp1[i1][j1] = find_max_no ( dp1 [ i1 ] [ j1 ] , dp1[q][i1] + 1);
answer = find_max_no(answer, dp1[i1][j1]);
}
}
hm1 . put ( arr1 [ i1 ] , i1 ) ;
}
return answer ;
}
public static void main ( String argvs [ ] )
{
LongestArithmeticProgression2 obj1 = new LongestArithmeticProgression2 ( ) ;
int arr1 [ ] = { 20 , 30 , 40 , 50 , 60 , 70 , 80 , 90 , 100 , 110 , 120 , 130 } ;
int size1 = arr1 . length ;
int longest_seq = obj1 . find_longest_ap_seq ( arr1 , size1 ) ;
System . out . println ( " For the following array: " ) ;
for ( int k1 = 0 ; k1 < size1 ; k1++ )
{
System . out . print ( arr1 [ k1 ] + " " ) ;
}
System . out . println ( " \n " ) ;
System . out . println ( " The length of the longest arithmetic progression sequence is: " + longest_seq ) ;
int arr2 [ ] = { 5 , 7 , 10 , 9 , 14 , 15 , 20 , 25 , 90 , 100 , 30, 40} ;
size1 = arr2 . length ;
longest_seq = obj1 . find_longest_ap_seq ( arr2 , size1 ) ;
System . out . println ( " \n " ) ;
System . out . println ( " For the following array: " ) ;
for ( int k1 = 0 ; k1 < size1 ; k1++ )
{
System . out . print ( arr2 [ k1 ] + " " ) ;
}
System . out . println ( " \n " ) ;
System . out . println ( " The length of the longest arithmetic progression sequence is : " + longest_seq) ;
}
}
Output:
Using Two Pointers Approach
With this method, we will try to determine the progression's previous and subsequent elements by fixing the central element of the arithmetic progression. Two points will be used to complete it. Before doing that, though, we must first sort the array. If the provided array is not sorted, the two-pointer approach will fail.
Java Program for longest arithmetic progression using Using Two Pointers Approach
import java . util . Arrays ;
public class Main
{
public int find_longest_ap_seq ( int arr1 [ ] , int size1 )
{
if(size1 <= 2)
{
return size1 ;
}
int answer = -1 ;
int dp1 [ ] = new int [ size1 ] ;
for ( int j1 = 0 ; j1 < size1 ; j1++ )
{
dp1 [ j1 ] = 2 ;
}
Arrays . sort ( arr1 ) ;
for ( int i1 = size1 – 2 ; i1 >= 0 ; i1-- )
{
int j1 = i1 – 1 ;
int k1 = i1 + 1 ;
while ( j1 >= 0 && k1 < size1 )
{
if ( arr1 [ j1 ] + arr1[ k1 ] == 2 * arr [ i1 ] )
{
dp1[i1] = Math . max ( dp1 [ k1 ] + 1, dp1 [ i1 ] ) ;
answer = Math . max ( answer , dp1 [ i1 ] ) ;
j1 = j1 – 1 ;
k1 = k1 + 1 ;
}
else if ( arr1 [ j1 ] + arr [ k1 ] < 2 * arr [ i1 ] )
{
k1 = k1 + 1 ;
}
else
{
j1 = j1 – 1 ;
}
}
}
return answer ;
}
public static void main ( String argvs [ ] )
{
Main obj1 = new Main ( ) ;
int inputArr [ ] = { 20 , 30 , 40 , 50 , 60 , 70 , 80 , 90 , 100 , 110 , 120 , 130 } ;
int size1 = arr1 . length ;
int longest_seq = obj1 . find_longest_ap_seq ( inputArr, size ) ;
System . out . println ( " For the following array: " ) ;
for ( int k1 = 0 ; k1 < size1 ; k1++ )
{
System . out . print ( arr1 [ k ] + " " ) ;
}
System . out . println ( " \n " ) ;
System . out . println ( " The length of the longest arithmetic progression sequence is: " + longest_seq ) ;
int arr2 [ ] = {5 , 7 , 10 , 9 , 14 , 15 , 20 , 25 , 90 , 100 , 30 , 40 } ;
size1 = arr2 . length ;
longest_seq = obj1 . find_longest_ap_seq ( arr2 , size1 ) ;
System . out . println ( " \n " ) ;
System . out . println ( " For the following array: " ) ;
for ( int k1 = 0 ; k1 < size1; k1++ )
{
System . out . print ( arr2 [ k1 ] + " " ) ;
}
System . out . println ( " \n " ) ;
System . out . println ( " The length of the longest arithmetic progression sequence is: " + longest_seq ) ;
}
} Output
Java Program4 for longest arithmetic progression
LongestArithmeticProgression4.java
import java . util . * ;
class LongestArithmeticProgression4
{
static int Answer ( int [ ] Arr )
{
int answer = 2 ;
int number = Arr . length ;
if ( number <= 2 )
return number ;
int [ ] ll = new int [ number ] ;
for ( int i1 = 0 ; i1 < number ; i1++ )
ll [ i1 ] = 2 ;
Arrays . sort ( Arr ) ;
for ( int j1 = number – 2 ; j1 >= 0 ; j1-- )
{
int i1 = j1 - 1;
int k1 = j1 + 1;
while (i1 >= 0 && k1 < number )
{
if ( Arr[ i1 ] + Arr [ k1 ] == 2 * Arr [ j1 ] )
{
ll [ j1 ] = Math . max ( ll [ k1 ] + 1 , ll [ j1 ] ) ;
answer = Math . max ( answer , ll [ j1 ] ) ;
i1 -= 1 ;
k1 += 1 ;
}
else if ( Arr [ i1 ] + Arr [ k1 ] < 2 * Arr [ j1 ] )
k1 += 1 ;
else
i1 -= 1 ;
}
}
return answer ;
}
public static void main ( String [ ] args )
{
int [ ] arr = { 5 , 7 , 10 , 9 , 14 , 15 , 20 , 25 , 90 , 100 , 30 , 13 } ;
System . out . print ( Answer ( arr ) + " \n " ) ;
}
}Output
