## 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.