Longest Arithmetic Sequence | DP – Part 24

Hello guys, welcome back to “code with asharam”. This is 24th part of my dynamic programming tutorials. I will discuss Longest Arithmetic Sequence in this part. If at any moment it feels like that things are going over your head, then, I advice to go through all the last tutorials. Even after that if you are stuck somewhere, then, feel free to leave a comment or send me a mail. I will answer your query as soon as possible. This is really an interesting problem. It will teach you the importance of iterative approach toward dynamic programming. I have discussed recursive approach until now but I will discuss this problem in iterative manner. Another fact which makes this problem interesting is that this was asked in Microsoft interview. So gear up guys to take a ride into deep oceans of dynamic programming.

Longest Arithmetic Sequence

Given an array $A[]$ of non-negative integers, the task is to find the length of longest arithmetic sequence. Note the fact that you can consider the array elements in any order.

Give it a try on your own before moving forward

Brute Force Approach

If you are not familiar with arithmetic sequences, then, you can give a read to this article before moving forward. Before doing anything, we will sort the array. You can get this idea from the fact that Arithmetic Progression is always sorted. Now, you know that the general term of an Arithmetic Progression is given by the relation $a+(n-1)*d$ where $a$ is first term and $d$ is common difference ($d = a_2-a_1$).

As you can see that the an Arithmetic Sequence can be represented by 3 parameters – $a_1$, $a_2$, $n$. In an array of $n$ integers, there can be $^nC_2$ different pairs of ($a_1, a_2$). For each pair, you can search for other terms of A.P. in $O(n)$ time. For $^nC_2$ pairs, the time complexity will be $O(n^3)$ time. Though this is lot better than exponential but still we can do better. Let’s see how?

Dynamic Programming Approach

As you all know that our method of solving problems using dynamic programming is an universal constant. We will play our game of guessing what is happening, what can or what cannot happen if we know something. Until now, we used to optimize the recursive relation used in brute force approach using memoization. But we don’t have any recursive relation in brute force solution this time. Nevertheless, we still have to optimize this solution. There is a simple catch if you observe carefully. Consider a arithmetic progression $a_1, a_2,……a_{m-1}, a_{m}$ of length $m$. In brute force solution we are finding length of longest arithmetic sequence for pairs ($a_1, a_2$), ($a_2, a_3$)…..($a_{m-1}, a_m$) as first 2 elements. But we just need to find length of longest arithmetic progression for pair ($a_1, a_2$) as other pairs will definitely result in smaller arithmetic sequence. And even if we want to find length of longest arithmetic sequence for other pairs, then, it can easily be done in $O(1)$ time as for an A.P. having starting pair ($a_i, a_{i+1}$), length of arithmetic progression will be $m-i+1$.
There is one more important point to consider. We are solving $m-2$ sub-problems if we start from 1st pair and $m-3$ sub-problems if we start from 2nd pair and so on, we are solving $(m-1)*(m-2)/2$ subproblems in total. So, instead of solving linear number of distinct sub-problems, we are solving quadratic number of overlapping sub-problems. This is the reason why our algorithm is becoming cubic instead of quadratic. So, let’s see what we can do to solve this problem.
We will maintain two arrays of size $nXn$. One will store the length of longest arithmetic sequence corresponding to each pair of first, second element and another array will store whether we have to solve the problem $(i, j)$ or not. If we have found an arithmetic sequence, then, we don’t have to visit the problem which have first 2 terms as consecutive terms of this AP. So, we have found the solution for our problems and it is finally time to write a code for this solution.

Code

#include <bits/stdc++.h>

using namespace std;

#define MAX 1001

int dp[MAX][MAX], arr[MAX];
bool shouldVisit[MAX][MAX];

int LLAP(int n) {

    // if n==1 then LLAP = 1 
    // if n==2 the LLAP = 2 
    if (n<3) return n;

    // sort the array in increasing order
    sort(arr+1, arr+n+1);

    memset(shouldVisit, true, sizeof(shouldVisit));

    /* if first term is in [arr[1]...arr[n-1]]
       then LLAP is atleast 2*/
    for (int i=1; i<n; i++) {
        for (int j=i+1; j<=n; j++) {
            dp[i][j] = 2;
        }
    }

    for (int i=1; i<n; i++) {
        for (int j=i+1; j<=n; j++) {
            if (shouldVisit[i][j]) {
                
                // Finding other terms of AP
                int d = arr[j] - arr[i], cur = arr[j];
                shouldVisit[i][j] = false;
                for (int k = i+1; k<=n; k++) {
                    if (cur+d == arr[k]) {
                        // We are only incrementing dp[i][j]
                        dp[i][j] += 1;
                        /* We don't need to solve problem for
                           as they are consecutive term of this
                           AP */
                        shouldVisit[j][k] = false;
                        // change cur
                        cur = arr[k];
                    }
                }

            }
        }
    }

    // Find maximum LLAP

    int maxLen = 1;
    for (int i=1; i<n; i++) {
        for (int j=i+1; j<=n; j++) {
            maxLen = max(maxLen, dp[i][j]);
        }
    }

    return maxLen;
}

int main() {

    arr[1] = 1, arr[2] = 7, arr[3] = 10,
    arr[4] = 15, arr[5] = 27, arr[6] = 30;

    int n = 6;
    cout << LLAP(n) << endl;

    // Output is 2
}

So, that’s it guys for today. I hope you would have enjoyed this tutorial. If you liked this tutorial, then, please follow my blog and share it with your friends. Meanwhile, don’t forget to solve HBIRD.
You can subscribe to my YouTube channel for video tutorials on dynamic programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: