'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: Dec 28, 2023

Longest arithmetic progression

gp-icon
Aptitude preparation
Free guided path
9 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

This blog will discuss the different approaches to finding the length of the longest arithmetic progression. 

Before jumping into the problem, let’s first understand arithmetic progression.

Arithmetic progression (AP)

An arithmetic progression (AP) is a sequence of numbers where the differences between two consecutive numbers are the same. 

For example, Sequence a0, a1, a2, a3, a4,.......... ak-1 of length k are in arithmetic progression if and only if a1 - a0 = a2 - a1 = a3 - a2 = a4 - a3 = ……… = an-1 - an-2.

The difference between any two consecutive numbers in an arithmetic progression is called the common difference.

Note: The common difference can be negative, positive or zero.

Problem statement

We are given an array having n elements in sorted order. Our task is to find the length of the longest arithmetic subsequence present in the given array.

Sample examples

Input1: a[] = [ 2, 5, 8, 11, 14, 15 ]

Output1: 5

Explanation: The longest arithmetic subsequence is ( 2, 5, 8, 11, 14 )

Length of the longest arithmetic progression = 5

 

Input2: a[] = [ 2, 4, 7, 9, 10 ]

Output2: 3

Explanation: The longest arithmetic subsequence is ( 4, 7, 10)

Length of the longest arithmetic progression = 3

Brute force approach

In this approach, we will use the basic property of an arithmetic progression. In an arithmetic progression, the difference between every two consecutive numbers is the same, so if we consider any pair (a1, a2) of numbers from the array, the next number in the arithmetic sequence will be a3 = a2 + common difference.

As a result, our problem is simple to solve. Take each pair of numbers and check whether the next number in the array exists or not using the arithmetic progression formula.

Steps of Algorithm

For each pair of numbers from the given array

  • Check if the next number exists or not in the array using the formula, i.e. next number = previous number + common difference.
  • If the next number exists, check for its next and maintain a max_len variable to store the length of the current longest arithmetic progression.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

int longestArithSeq(int a[], int n) {
    if (n <= 2)
        return n;

    int maxLength = 2;

    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int diff = a[j] - a[i];
            int next_num = a[j] + diff;
            int curr_len = 2;

            for (int k = 0; k < n; k++)
            {
                if (a[k] == next_num) {
                    curr_len += 1;
                    maxLength = max(maxLength, curr_len);
                    next_num = next_num + diff;
                }
            }
        }
    }
    return maxLength;
}

int main()
{
    int a[] = { 2, 4, 9, 7, 10 }; //given array

    int n = sizeof(a) / sizeof(a[0]);    // size of array

    cout << longestArithSeq(a, n);

    return 0;
}

 

Output:

3

 

Complexity Analysis

Time complexity: We have used 3 nested loops so, the time complexity is O(n^3), where n is the number of elements in the given array.

Space complexity: O(1) as we have used constant extra space.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Dynamic programming approach

When we recalculate the length of an arithmetic progression for a pair of numbers using the brute force method described above, we find overlapping cases. So we can think of an efficient approach using dynamic programming.

The idea is to create a 2D table dp[n][n]. The Longest arithmetic progression is stored in this table as dp[i][j], with a[i] and a[j] as the first two elements of AP and (j > i).

The table's last column is always 2, as the minimum length of arithmetic progression will be 2 if n>2. 

The table will be filled from the right bottom to the left top. Now, to fill the rest of the table. First, fix j (AP's second element).

Now, the values of i and k are looked for in order to find a fixed j. If the values of i, j and k are found to form an AP, the value of dp[i][j] is set to dp[j][k] + 1.

Note: Because the loop traverses from right to left columns, the value of dp[j][k] must have been filled previously.

Steps of algorithm

  1. Fill the last column with 2.
  2. Fix j = n-1 to 1 and perform the following steps for each j:
  • Find all i and k such that the numbers a[i], a[j], and a[k] form the letter AP.
  • Fill dp[i][j] = 1 + dp[j][k]
  • It should be updated if dp[i][j] is longer than the current maximum length.
  • A small optimization change: if nums[i] + nums[k] > 2*nums[j], we can safely fill nums[i][j] with 2.
  • While i > 0 even after k > n, fill all dp[i][j] = 2.

 

For example

If a[] = [ 2, 5, 8, 11, 14, 15 ], the table will look like this:
 

 

The rest of the boxes contain garbage values.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

int longest_ap(int a[], int n)
{
    if (n <= 2)
        return n;

    int dp[n][n];
    int max_len = 2;

    for (int i = 0; i < n; i++) // filling last column as 2
        dp[i][n - 1] = 2;

    // Consider every element as the second element of AP
    for (int j = n - 2; j >= 1; j--)
    {
        int i = j - 1;
        int k = j + 1;

        while (i >= 0 && k <= n - 1)
        {
            if (a[i] + a[k] < 2 * a[j])
                k = k + 1;
            else if (a[i] + a[k] > 2 * a[j])
            {
                dp[i][j] = 2;
                i = i - 1;
            }
            else {
                dp[i][j] = dp[j][k] + 1 ;
                max_len = max(max_len, dp[i][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 max_len;
}

int main()
{
    int a[] = {1, 3, 5, 6, 7, 8}; //given array

    int n = sizeof(a) / sizeof(a[0]);    // size of array

    cout << longest_ap(a, n);

    return 0;
}

 

Output:

3

 

Complexity Analysis

Time complexity: We have used two nested loops, so the time complexity is O(n^2), where n is the number of elements in the given array.

Space complexity: O(n^2) as we have used a 2D table of size (n*n).

Space optimised dynamic programming approach

We can further optimise the space complexity of the above algorithm. The idea is to use an array to store the results instead of a 2D table.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int longestAP(int a[], int n)
{
    if (n <= 2)
        return n;

    int max_len = 2;

    int dp[n];

    for (int i = 0; i < n; i++)
    {
        dp[i] = 2;
    }

    for (int j = n - 2; j >= 0; j--)
    {
        int i = j - 1;
        int k = j + 1;

        while (i >= 0 && k < n)
        {
            if (a[i] + a[k] == 2 * a[j])
            {
                dp[j] = max(dp[k] + 1, dp[j]);
                max_len = max(max_len, dp[j]);
                i--;
                k++;
            }
            else if (a[i] + a[k] < 2 * a[j])
                k++;
            else
                i--;
        }
    }
    return max_len;
}

int main()
{
    int a[] = { 2, 4, 7, 9, 10 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << longestAP(a, n) << endl;
    return 0;
}

 

Output:

3

 

Complexity Analysis

Time complexity: We have used two nested loops, so the time complexity is O(n^2), where n is the number of elements in the given array.

Space complexity: O(n) as we have used an array of size n.

Check out this : Longest common subsequence

Frequently asked questions

Q1. Is it possible for a negative sequence to be arithmetic?

Ans: Yes, an arithmetic sequence's common difference can be negative. A common difference occurs between two consecutive numbers in an arithmetic sequence.

 

Q2. What do you call numbers that appear in an arithmetic sequence between two non-consecutive terms?

Ans: The difference between any two consecutive terms in an arithmetic sequence is always the same. The common difference is the constant that exists between two consecutive terms. A common difference is a number added to any one term of an arithmetic sequence to generate the next term.

 

Q3. Is it true that dynamic programming is preferable to memoization?

Ans: Memorization is usually accomplished through recursion in coding, whereas dynamic programming uses iteration to perform calculations. If you carefully calculate your algorithm’s space and time complexity, a dynamic programming-style implementation can provide you with better results.

Key Takeaways

This article discussed arithmetic progression and the different approaches to finding the length of the longest arithmetic progression. We discussed the brute force approach and a dynamic programming approach to solve the problem with examples.

If you are a beginner, interested in coding and want to learn DSA, you can look for our guided path for DSA, which is free! 

Thank you for reading!

Previous article
Progressions - Arithmetic, Geometric and Harmonic progression(AP, GP, HP)
Next article
Difference between Log and Ln(Natural Log)
Guided path
Free
gridgp-icon
Aptitude preparation
9 chapters
190+ Problems
gp-badge
Earn badges and level up
Live masterclass