## Longest Arithmetic Progression Difficulty: Medium

#### Understanding The Problem

Problem Description

Given a set of integers in an array ``` A[] ``` of size ``` n ``` , write a program to find the length of the longest arithmetic subsequence in ``` A ``` .

In other wrods, find the longest sequence of indices, ``` 0 <= i1 < i2 < … < ik <= n-1 ``` such that sequence ``` A[i1], A[i2], …, A[ik] ``` is an Arithmetic Progression.

Problem Note:

• Arithmetic Progression is a sequence in which all the differences between consecutive pairs are the same, i.e sequence P, P, P, …, P[m — 1] of length m is an Arithmetic Progression if and only if P — P == P — P == P — P == … == P[m — 1] — P[m — 2]
• The common difference can be positive, negative or 0.

Example 1

``````Input: A[] = [3, 6, 9, 12]
Output: 4
Explanation: [3, 6, 9, 12] form an arithmetic progression.``````

Example 2

``````Input: A[] = [9, 4, 7, 2, 10]
Output: 3
Explanation:[4, 7, 10] form an arithmetic progression.``````

#### Solutions

We will be discussing two different solutions for this problem

1. Brute Force Solution: For every pair of numbers in the array, check if the second number + their difference exists in the array and maintain the count accordingly.
2. Dynamic Programming: Store the number of sequences for each pair of numbers and fill the DP table.

You may try to solve this problem here.

#### 1. Brute Force Solution

An arithmetic progression(AP) is a sequence of numbers in which each differs from the preceding one by a constant quantity. If we consider any pair ``` ( 1st_num , 2nd_num ) ``` of numbers from the array, then the next number in the arithmetic sequence will be ``` ( 2nd_num + diff ) ``` where ``` diff ``` is ``` ( 2nd_num — 1st_num ) ``` from the formula. This makes our problem easy to solve. We just have to take each pair of numbers and check if the next number following the formula of AP exists or not in the array.

If the next number of the series considering the ``` pair(1st_num, 2nd_num) ``` exists then, we will have to look for the ``` 3rd_num + diff ``` and thus maintain a counter to keep track of the maximum length of such a sequence.

Solution Steps

1. For each pair of numbers from the ``` nums ``` array
• check if the next number ``` (3rd_num) = 2nd_num + diff ``` exists
• If the ``` 3rd_num ``` exists, then look for ``` 4th_num = 3rd_num + diff ``` exists and so on.

2. Maintain a ``` maxLength ``` variable that will tell about the maximum length of an AP that exists in the ``` nums ``` array.

Pseudo Code

``````int longestArithSeqLength(int[] nums) {
if(nums.size() <= 2){
return nums.size()
}
maxLength = 2
for(int i=0 to i < nums.size()){
for(int j=i+1 to j < nums.size()){
diff = nums[j] - nums[i]
nextTarget = nums[j] + diff
currentLongestLength = 2
for(int k = 0 to k < nums.size()){
if(nums[k] == nextTarget){
currentLongestLength += 1
maxLength = max(maxLength, currentLongestLength)
nextTarget = nextTarget + diff
}
}
}
}
return maxLength
}``````

Complexity Analysis

Time Complexity: O(n³)

Space Complexity: O(1)

Critical Ideas to Think

• How did we find the next number of the sequence for each valid AP sequence?
• The ``` currentLongestLength ``` contains the longest sequence of AP for which elements?
• Try to dry run the code on some example and check for overlapping problems.

#### 2. Dynamic Programming

If we analyze the above brute force solution, we will find that there are overlapping cases when we recalculate the length of an arithmetic progression for a pair of numbers.

The idea is to create a 2D table dp[n][n]. An entry ``` dp[i][j] ``` in this table stores the Longest arithmetic progression with ``` nums[i] ``` and ``` nums[j] ``` as the first two elements of AP and ``` (j > i) ``` . The last column of the table is always 2 (as discussed above). The rest of the table is filled from the bottom right to top left. To fill the rest of the table, ``` j ``` (second element in AP) is first fixed . ``` i ``` and ``` k ``` are searched for a fixed ``` j ``` . If ``` i ``` and ``` k ``` are found such that ``` i , j , k ``` form an AP, then the value of ``` dp[i][j] ``` is set as ``` dp[j][k] + 1 ``` . Note that the value of ``` dp[j][k] ``` must have been filled before as the loop traverses from right to left columns.

Solution Steps

1. For j = n, ``` dp[i][j] = 2 ``` for ``` 0<i<n ``` , bottom-most column filled with ``` 2 ``` .
2. Fix ``` j = n-1 ``` to ``` 1 ``` and for each ``` j ``` do the below steps:
• Find all ``` i ``` and ``` k ``` such that ``` nums[i] , nums[j] and nums[k] ``` form AP.
• Fill ``` dp[i][j] = 1 + dp[j][k] ```
• Check if ``` dp[i][j] ``` is longer than the current max length, if yes, update it.
• A slight change for optimization, if ``` nums[i] + nums[k] > 2*nums[j] ``` , we can safely fill ``` nums[i][j] as 2 ``` .
• While ``` i > 0 ``` even after ``` k > n ``` , fill all ``` dp[i][j] = 2 ``` .

Pseudo Code

``````int lenghtOfLongestAP(int[] nums)
{
n = nums.size()
int dp[n][n]
int longestAP = 2
// Fill entries in last column as 2.
for (int i = 0 to i < n)
dp[i][n-1] = 2
// Consider every element as second element of AP
for (int j=n-2 to j>=1) {
i = j-1
k = j+1
while (i >= 0 and k <= n-1) {
if (nums[i] + nums[k] <= 2*nums[j])
k = k + 1
else if (nums[i] + nums[k] > 2*nums[j]) {
dp[i][j] = 2
i = i - 1
}
else {
dp[i][j] = dp[j][k] + 1
longestAP = max(longestAP, dp[i][j])
// Change i and k to fill more dp[i][j] values for
// current j
i = i - 1
k = k + 1
}
}
// If the loop was stopped due to k becoming more than
// n-1, set the remaining entties in column j as 2
while (i >= 0) {
dp[i][j] = 2
i = i - 1
}
}
return longestAP
}``````

Complexity Analysis

Time Complexity: O(n²)

Space Complexity: O(n²)

Critical Ideas to Think

• Why did we initialize the ``` DP[i][n-i] ``` with ``` 2 ``` ?
• What did we insert in ``` DP[i][j] ``` when ``` nums[i] + nums[k] > 2*nums[j] ``` and why?
• What is the meaning of the value stored in ``` DP[i][j] ``` ? What does the value represent?

#### Comparison of Solutions #### Suggested Problems to Solve

• Longest arithmetic progression with the given common difference
• The ratio of mth and nth term in an Arithmetic Progression (AP)
• Program for N-th term of Arithmetic Progression series
• Check whether Arithmetic Progression can be formed from the given array
• Find the missing number in Arithmetic Progression
• Count of AP (Arithmetic Progression) Subsequences in an array

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

Happy Coding! Enjoy Algorithms!