Longest arithmetic progression

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

3

You can also try this code with Online C++ Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

3

You can also try this code with Online C++ Compiler

Run Code

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!