# Find the length of longest arithmetic progression

In the realm of computer science and mathematics, the challenge of discovering patterns within data is a fundamental pursuit. One such problem entails finding the length of the longest arithmetic progression within a sorted array. This problem holds significance in various domains, from data analysis to algorithm optimization. In this article, we will delve into the intricacies of this problem, explore a dynamic programming approach to its solution, and elucidate the steps involved using code examples.

## Problem Statement

Given a sorted array of integers, the task is to determine the length of the longest arithmetic progression within the array. An arithmetic progression is a sequence of numbers in which the difference between any two consecutive terms is constant.

## Example

Consider the sorted array:

``Element: 5 8 10 12 14 16 15``

The longest arithmetic progression in this array is "8, 10, 12, 14, 16" with a common difference of 2. Therefore, the length of this arithmetic progression is 5.

## Idea to Solve

To tackle this problem efficiently, we employ a dynamic programming approach. The fundamental insight lies in using a two-dimensional array to store information about the length of arithmetic progressions that conclude at specific indices.

## Algorithm

1. Initialize the result as 2, since the minimum length of an arithmetic progression is 2.
2. Create a 2D array named `auxiliary` with all values initialized to 2. This array will store information about the length of arithmetic progressions ending at specific indices.
3. Loop through the array in reverse order, starting from the second-to-last element. a. For each index `j`, maintain two pointers: `i` (before `j`) and `k` (after `j`). b. While `i` is greater than or equal to 0 and `k` is within bounds: i. If `data[i] + data[k]` is less than `2 * data[j]`, increment `k`. ii. If `data[i] + data[k]` is greater than `2 * data[j]`, set `auxiliary[i][j]` to 2 and decrement `i`. iii. If `data[i] + data[k]` is equal to `2 * data[j]`, set `auxiliary[i][j]` to `auxiliary[j][k] + 1`, update the result if needed, increment `k`, and decrement `i`. c. After the inner loop, set any remaining `i` values to 2, as no valid arithmetic progression can be formed with those. d. Move to the previous index `j`.
4. Print the final result.

## Code Solution

``````// C program
// Find the length of longest arithmetic progression
// In sorted data

#include <stdio.h>

//Display the elements of array
void print_data(int data[], int size)
{
printf("\n Element :");
for (int i = 0; i < size; ++i)
{
printf("  %d", data[i]);
}
}
//returns the maximum of given two numbers
int max_num(int a, int b)
{
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
void length_of_longest_ap(int data[], int size)
{
//Display given element
print_data(data, size);
printf("\n Result  : ");
if (size <= 2)
{
//When have two or less than 2 elements
printf(" %d\n", size);
return;
}
//Minimum 2 result are possible
int result = 2;
//Create storage to calculate result
int auxiliary[size][size];
//Loop controlling variables
int i = 0;
int j = 0;
int k = 0;
//Set initial value of created storage
for (i = 0; i < size; i++)
{
// Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data[i] + data[k] < 2 * data[j])
{
k++;
}
else if (data[i] + data[k] > 2 * data[j])
{
auxiliary[i][j] = 2;
i--;
}
else
{
auxiliary[i][j] = auxiliary[j][k] + 1;
//Get result
result = max_num(result, auxiliary[i][j]);
k++;
i--;
}
}
while (i >= 0)
{
auxiliary[i][j] = 2;
i--;
}
j--;
}
printf(" %d\n", result);
}
int main()
{
//Define the collection of sorted integer values
//This is test inputs
int data1[] = {
-3,
0,
3,
7,
9,
12,
14,
15,
19,
21,
27
};
int data2[] = {
8,
10,
12,
14,
17
};
int data3[] = {
5,
8,
10,
12,
14,
16,
15
};
int data4[] = {
1,
3,
5,
7,
9,
11,
13
};
//Get the size of given data1
int size = sizeof(data1) / sizeof(data1[0]);
length_of_longest_ap(data1, size);
//Get the size of given data2
size = sizeof(data2) / sizeof(data2[0]);
length_of_longest_ap(data2, size);
//Get the size of given data3
size = sizeof(data3) / sizeof(data3[0]);
length_of_longest_ap(data3, size);
//Get the size of given data4
size = sizeof(data4) / sizeof(data4[0]);
length_of_longest_ap(data4, size);
return 0;
}``````

#### Output

`````` Element :  -3  0  3  7  9  12  14  15  19  21  27
Result  :  6

Element :  8  10  12  14  17
Result  :  4

Element :  5  8  10  12  14  16  15
Result  :  5

Element :  1  3  5  7  9  11  13
Result  :  7``````
``````// Java program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
//Display the elements of array
public void print_data(int[] data, int size)
{
System.out.print("\n Element :");
for (int i = 0; i < size; ++i)
{
System.out.print("  " + data[i] );
}
}
//returns the maximum of given two numbers
public int max_num(int a, int b)
{
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
public void length_of_longest_ap(int[] data, int size)
{
//Display given element
print_data(data, size);
System.out.print("\n Result : ");
if (size <= 2)
{
//When have two or less than 2 elements
System.out.print("  " + size + "\n");
return;
}
//Minimum 2 result are possible
int result = 2;
//Create storage to calculate result
int[][] auxiliary = new int[size][size];
//Loop controlling variables
int i = 0;
int j = 0;
int k = 0;
//Set initial value of created storage
for (i = 0; i < size; i++)
{
// Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data[i] + data[k] < 2 * data[j])
{
k++;
}
else if (data[i] + data[k] > 2 * data[j])
{
auxiliary[i][j] = 2;
i--;
}
else
{
auxiliary[i][j] = auxiliary[j][k] + 1;
//Get result
result = max_num(result, auxiliary[i][j]);
k++;
i--;
}
}
while (i >= 0)
{
auxiliary[i][j] = 2;
i--;
}
j--;
}
System.out.print("  " + result + "\n");
}
public static void main(String[] args)
{
ArithmeticProgression obj = new ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
int[] data1 = {
-3,
0,
3,
7,
9,
12,
14,
15,
19,
21,
27
};
int[] data2 = {
8,
10,
12,
14,
17
};
int[] data3 = {
5,
8,
10,
12,
14,
16,
15
};
int[] data4 = {
1,
3,
5,
7,
9,
11,
13
};
//Get the size of given data1
int size = data1.length;
obj.length_of_longest_ap(data1, size);
//Get the size of given data2
size = data2.length;
obj.length_of_longest_ap(data2, size);
//Get the size of given data3
size = data3.length;
obj.length_of_longest_ap(data3, size);
//Get the size of given data4
size = data4.length;
obj.length_of_longest_ap(data4, size);
}
}``````

#### Output

`````` Element :  -3  0  3  7  9  12  14  15  19  21  27
Result :   6

Element :  8  10  12  14  17
Result :   4

Element :  5  8  10  12  14  16  15
Result :   5

Element :  1  3  5  7  9  11  13
Result :   7``````
``````//Include header file
#include <iostream>

using namespace std;
// C++ program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
public:
//Display the elements of array
void print_data(int data[], int size)
{
cout << "\n Element :";
for (int i = 0; i < size; ++i)
{
cout << "  " << data[i];
}
}
//returns the maximum of given two numbers
int max_num(int a, int b)
{
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
void length_of_longest_ap(int data[], int size)
{
//Display given element
this->print_data(data, size);
cout << "\n Result : ";
if (size <= 2)
{
//When have two or less than 2 elements
cout << "  " << size << "\n";
return;
}
//Minimum 2 result are possible
int result = 2;
//Create storage to calculate result
int auxiliary[size][size];
//Loop controlling variables
int i = 0;
int j = 0;
int k = 0;
//Set initial value of created storage
for (i = 0; i < size; i++)
{
// Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data[i] + data[k] < 2 * data[j])
{
k++;
}
else if (data[i] + data[k] > 2 * data[j])
{
auxiliary[i][j] = 2;
i--;
}
else
{
auxiliary[i][j] = auxiliary[j][k] + 1;
//Get result
result = this->max_num(result, auxiliary[i][j]);
k++;
i--;
}
}
while (i >= 0)
{
auxiliary[i][j] = 2;
i--;
}
j--;
}
cout << "  " << result << "\n";
}
};
int main()
{
ArithmeticProgression obj = ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
int data1[] = {
-3 , 0 , 3 , 7 , 9 , 12 , 14 , 15 , 19 , 21 , 27
};
int data2[] = {
8 , 10 , 12 , 14 , 17
};
int data3[] = {
5 , 8 , 10 , 12 , 14 , 16 , 15
};
int data4[] = {
1 , 3 , 5 , 7 , 9 , 11 , 13
};
//Get the size of given data1
int size = sizeof(data1) / sizeof(data1[0]);
obj.length_of_longest_ap(data1, size);
//Get the size of given data2
size = sizeof(data2) / sizeof(data2[0]);
obj.length_of_longest_ap(data2, size);
//Get the size of given data3
size = sizeof(data3) / sizeof(data3[0]);
obj.length_of_longest_ap(data3, size);
//Get the size of given data4
size = sizeof(data4) / sizeof(data4[0]);
obj.length_of_longest_ap(data4, size);
return 0;
}``````

#### Output

`````` Element :  -3  0  3  7  9  12  14  15  19  21  27
Result :   6

Element :  8  10  12  14  17
Result :   4

Element :  5  8  10  12  14  16  15
Result :   5

Element :  1  3  5  7  9  11  13
Result :   7``````
``````//Include namespace system
using System;

// C# program
// Find the length of longest arithmetic progression
// In sorted data

class ArithmeticProgression
{
//Display the elements of array
public void print_data(int[] data, int size)
{
Console.Write("\n Element :");
for (int i = 0; i < size; ++i)
{
Console.Write("  " + data[i]);
}
}
//returns the maximum of given two numbers
public int max_num(int a, int b)
{
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
public void length_of_longest_ap(int[] data, int size)
{
//Display given element
print_data(data, size);
Console.Write("\n Result : ");
if (size <= 2)
{
//When have two or less than 2 elements
Console.Write("  " + size + "\n");
return;
}
//Minimum 2 result are possible
int result = 2;
//Create storage to calculate result
int[,] auxiliary = new int[size,size];
//Loop controlling variables
int i = 0;
int j = 0;
int k = 0;
//Set initial value of created storage
for (i = 0; i < size; i++)
{
// Set the [i] row and last column value is to 2
auxiliary[i,size - 1] = 2;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data[i] + data[k] < 2 * data[j])
{
k++;
}
else if (data[i] + data[k] > 2 * data[j])
{
auxiliary[i,j] = 2;
i--;
}
else
{
auxiliary[i,j] = auxiliary[j,k] + 1;
//Get result
result = max_num(result, auxiliary[i,j]);
k++;
i--;
}
}
while (i >= 0)
{
auxiliary[i,j] = 2;
i--;
}
j--;
}
Console.Write("  " + result + "\n");
}
public static void Main(String[] args)
{
ArithmeticProgression obj = new ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
int[] data1 = {
-3 , 0 , 3 , 7 , 9 , 12 , 14 , 15 , 19 , 21 , 27
};
int[] data2 = {
8 , 10 , 12 , 14 , 17
};
int[] data3 = {
5 , 8 , 10 , 12 , 14 , 16 , 15
};
int[] data4 = {
1 , 3 , 5 , 7 , 9 , 11 , 13
};
//Get the size of given data1
int size = data1.Length;
obj.length_of_longest_ap(data1, size);
//Get the size of given data2
size = data2.Length;
obj.length_of_longest_ap(data2, size);
//Get the size of given data3
size = data3.Length;
obj.length_of_longest_ap(data3, size);
//Get the size of given data4
size = data4.Length;
obj.length_of_longest_ap(data4, size);
}
}``````

#### Output

`````` Element :  -3  0  3  7  9  12  14  15  19  21  27
Result :   6

Element :  8  10  12  14  17
Result :   4

Element :  5  8  10  12  14  16  15
Result :   5

Element :  1  3  5  7  9  11  13
Result :   7``````
``````<?php
// Php program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
//Display the elements of array
public	function print_data( & \$data, \$size)
{
echo "\n Element :";
for (\$i = 0; \$i < \$size; ++\$i)
{
echo "  ". \$data[\$i];
}
}
//returns the maximum of given two numbers
public	function max_num(\$a, \$b)
{
if (\$a > \$b)
{
//When (a) is greater
return \$a;
}
//When b is greater than or equal to a
return \$b;
}
//returns the length of longest arithmetic progression
public	function length_of_longest_ap( & \$data, \$size)
{
//Display given element
\$this->print_data(\$data, \$size);
echo "\n Result : ";
if (\$size <= 2)
{
//When have two or less than 2 elements
echo "  ". \$size ."\n";
return;
}
//Minimum 2 result are possible
\$result = 2;
//Create storage to calculate result
\$auxiliary = array_fill(0, \$size,  array_fill(0, \$size, 0));
//Loop controlling variables
\$i = 0;
\$j = 0;
\$k = 0;
//Set initial value of created storage
for (\$i = 0; \$i < \$size; \$i++)
{
// Set the [i] row and last column value is to 2
\$auxiliary[\$i][\$size - 1] = 2;
}
// Get last-1 position of given data
\$j = \$size - 2;
while (\$j >= 1)
{
\$k = \$j + 1;
\$i = \$j - 1;
while (\$i >= 0 && \$k <= \$size - 1)
{
if (\$data[\$i] + \$data[\$k] < 2 * \$data[\$j])
{
\$k++;
}
else if (\$data[\$i] + \$data[\$k] > 2 * \$data[\$j])
{
\$auxiliary[\$i][\$j] = 2;
\$i--;
}
else
{
\$auxiliary[\$i][\$j] = \$auxiliary[\$j][\$k] + 1;
//Get result
\$result = \$this->max_num(\$result, \$auxiliary[\$i][\$j]);
\$k++;
\$i--;
}
}
while (\$i >= 0)
{
\$auxiliary[\$i][\$j] = 2;
\$i--;
}
\$j--;
}
echo "  ". \$result ."\n";
}
}

function main()
{
\$obj = new ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
\$data1 = array(-3, 0, 3, 7, 9, 12, 14, 15, 19, 21, 27);
\$data2 = array(8, 10, 12, 14, 17);
\$data3 = array(5, 8, 10, 12, 14, 16, 15);
\$data4 = array(1, 3, 5, 7, 9, 11, 13);
//Get the size of given data1
\$size = count(\$data1);
\$obj->length_of_longest_ap(\$data1, \$size);
//Get the size of given data2
\$size = count(\$data2);
\$obj->length_of_longest_ap(\$data2, \$size);
//Get the size of given data3
\$size = count(\$data3);
\$obj->length_of_longest_ap(\$data3, \$size);
//Get the size of given data4
\$size = count(\$data4);
\$obj->length_of_longest_ap(\$data4, \$size);
}
main();``````

#### Output

`````` Element :  -3  0  3  7  9  12  14  15  19  21  27
Result :   6

Element :  8  10  12  14  17
Result :   4

Element :  5  8  10  12  14  16  15
Result :   5

Element :  1  3  5  7  9  11  13
Result :   7``````
``````// Node Js program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
//Display the elements of array
print_data(data, size)
{
process.stdout.write("\n Element :");
for (var i = 0; i < size; ++i)
{
process.stdout.write("  " + data[i]);
}
}
//returns the maximum of given two numbers
max_num(a, b)
{
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
length_of_longest_ap(data, size)
{
//Display given element
this.print_data(data, size);
process.stdout.write("\n Result : ");
if (size <= 2)
{
//When have two or less than 2 elements
process.stdout.write("  " + size + "\n");
return;
}
//Minimum 2 result are possible
var result = 2;
//Create storage to calculate result
var auxiliary = Array(size).fill(0).map(() => new Array(size).fill(0));
//Loop controlling variables
var i = 0;
var j = 0;
var k = 0;
//Set initial value of created storage
for (i = 0; i < size; i++)
{
// Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data[i] + data[k] < 2 * data[j])
{
k++;
}
else if (data[i] + data[k] > 2 * data[j])
{
auxiliary[i][j] = 2;
i--;
}
else
{
auxiliary[i][j] = auxiliary[j][k] + 1;
//Get result
result = this.max_num(result, auxiliary[i][j]);
k++;
i--;
}
}
while (i >= 0)
{
auxiliary[i][j] = 2;
i--;
}
j--;
}
process.stdout.write("  " + result + "\n");
}
}

function main()
{
var obj = new ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
var data1 = [-3, 0, 3, 7, 9, 12, 14, 15, 19, 21, 27];
var data2 = [8, 10, 12, 14, 17];
var data3 = [5, 8, 10, 12, 14, 16, 15];
var data4 = [1, 3, 5, 7, 9, 11, 13];
//Get the size of given data1
var size = data1.length;
obj.length_of_longest_ap(data1, size);
//Get the size of given data2
size = data2.length;
obj.length_of_longest_ap(data2, size);
//Get the size of given data3
size = data3.length;
obj.length_of_longest_ap(data3, size);
//Get the size of given data4
size = data4.length;
obj.length_of_longest_ap(data4, size);
}
main();``````

#### Output

`````` Element :  -3  0  3  7  9  12  14  15  19  21  27
Result :   6

Element :  8  10  12  14  17
Result :   4

Element :  5  8  10  12  14  16  15
Result :   5

Element :  1  3  5  7  9  11  13
Result :   7``````
``````#  Python 3 program
#  Find the length of longest arithmetic progression
#  In sorted data
class ArithmeticProgression :
# Display the elements of array
def print_data(self, data, size) :
print("\n Element :", end = "")
i = 0
while (i < size) :
print("  ", data[i], end = "")
i += 1

# returns the maximum of given two numbers
def max_num(self, a, b) :
if (a > b) :
# When (a) is greater
return a

# When b is greater than or equal to a
return b

# returns the length of longest arithmetic progression
def length_of_longest_ap(self, data, size) :
# Display given element
self.print_data(data, size)
print("\n Result : ", end = "")
if (size <= 2) :
# When have two or less than 2 elements
print("  ", size ,"\n", end = "")
return

# Minimum 2 result are possible
result = 2
# Create storage to calculate result
auxiliary =[[0 for x in range(size)] for y in range(size)]

# Loop controlling variables
i = 0
j = 0
k = 0
# Set initial value of created storage
i = 0
while (i < size) :
#  Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2
i += 1

#  Get last-1 position of given data
j = size - 2
while (j >= 1) :
k = j + 1
i = j - 1
while (i >= 0 and k <= size - 1) :
if (data[i] + data[k] < 2 * data[j]) :
k += 1

elif(data[i] + data[k] > 2 * data[j]) :
auxiliary[i][j] = 2
i -= 1
else :
auxiliary[i][j] = auxiliary[j][k] + 1
# Get result
result = self.max_num(result, auxiliary[i][j])
k += 1
i -= 1

while (i >= 0) :
auxiliary[i][j] = 2
i -= 1

j -= 1

print("  ", result ,"\n", end = "")

def main() :
obj = ArithmeticProgression()
# Define the collection of sorted integer values
# This is test inputs
data1 = [-3, 0, 3, 7, 9, 12, 14, 15, 19, 21, 27]
data2 = [8, 10, 12, 14, 17]
data3 = [5, 8, 10, 12, 14, 16, 15]
data4 = [1, 3, 5, 7, 9, 11, 13]
# Get the size of given data1
size = len(data1)
obj.length_of_longest_ap(data1, size)
# Get the size of given data2
size = len(data2)
obj.length_of_longest_ap(data2, size)
# Get the size of given data3
size = len(data3)
obj.length_of_longest_ap(data3, size)
# Get the size of given data4
size = len(data4)
obj.length_of_longest_ap(data4, size)

if __name__ == "__main__": main()``````

#### Output

`````` Element :   -3   0   3   7   9   12   14   15   19   21   27
Result :    6

Element :   8   10   12   14   17
Result :    4

Element :   5   8   10   12   14   16   15
Result :    5

Element :   1   3   5   7   9   11   13
Result :    7``````
``````#  Ruby program
#  Find the length of longest arithmetic progression
#  In sorted data
class ArithmeticProgression

# Display the elements of array
def print_data(data, size)

print("\n Element :")
i = 0
while (i < size)

print("  ", data[i])
i += 1
end
end
# returns the maximum of given two numbers
def max_num(a, b)

if (a > b)

# When (a) is greater
return a
end
# When b is greater than or equal to a
return b
end
# returns the length of longest arithmetic progression
def length_of_longest_ap(data, size)

# Display given element
self.print_data(data, size)
print("\n Result : ")
if (size <= 2)

# When have two or less than 2 elements
print("  ", size ,"\n")
return
end
# Minimum 2 result are possible
result = 2
# Create storage to calculate result
auxiliary = Array.new(size) {Array.new(size){0}}
# Loop controlling variables
i = 0
j = 0
k = 0
# Set initial value of created storage
i = 0
while (i < size)

#  Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2
i += 1
end
#  Get last-1 position of given data
j = size - 2
while (j >= 1)

k = j + 1
i = j - 1
while (i >= 0 && k <= size - 1)

if (data[i] + data[k] < 2 * data[j])

k += 1
elsif(data[i] + data[k] > 2 * data[j])

auxiliary[i][j] = 2
i -= 1
else

auxiliary[i][j] = auxiliary[j][k] + 1
# Get result
result = self.max_num(result, auxiliary[i][j])
k += 1
i -= 1
end
end
while (i >= 0)

auxiliary[i][j] = 2
i -= 1
end
j -= 1
end
print("  ", result ,"\n")
end
end
def main()

obj = ArithmeticProgression.new()
# Define the collection of sorted integer values
# This is test inputs
data1 = [-3, 0, 3, 7, 9, 12, 14, 15, 19, 21, 27]
data2 = [8, 10, 12, 14, 17]
data3 = [5, 8, 10, 12, 14, 16, 15]
data4 = [1, 3, 5, 7, 9, 11, 13]
# Get the size of given data1
size = data1.length
obj.length_of_longest_ap(data1, size)
# Get the size of given data2
size = data2.length
obj.length_of_longest_ap(data2, size)
# Get the size of given data3
size = data3.length
obj.length_of_longest_ap(data3, size)
# Get the size of given data4
size = data4.length
obj.length_of_longest_ap(data4, size)
end
main()``````

#### Output

`````` Element :  -3  0  3  7  9  12  14  15  19  21  27
Result :   6

Element :  8  10  12  14  17
Result :   4

Element :  5  8  10  12  14  16  15
Result :   5

Element :  1  3  5  7  9  11  13
Result :   7
``````
``````// Scala program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
//Display the elements of array
def print_data(data: Array[Int], size: Int): Unit = {
print("\n Element :");
var i: Int = 0;
while (i < size)
{
print("  " + data(i));
i += 1;
}
}
//returns the maximum of given two numbers
def max_num(a: Int, b: Int): Int = {
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
def length_of_longest_ap(data: Array[Int], size: Int): Unit = {
//Display given element
print_data(data, size);
print("\n Result : ");
if (size <= 2)
{
//When have two or less than 2 elements
print("  " + size + "\n");
return;
}
//Minimum 2 result are possible
var result: Int = 2;
//Create storage to calculate result
var auxiliary: Array[Array[Int]] = Array.fill[Int](size,size)(0);
//Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
//Set initial value of created storage
i = 0;
while (i < size)
{
// Set the [i] row and last column value is to 2
auxiliary(i)(size - 1) = 2;
i += 1;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data(i) + data(k) < 2 * data(j))
{
k += 1;
}
else if (data(i) + data(k) > 2 * data(j))
{
auxiliary(i)(j) = 2;
i -= 1;
}
else
{
auxiliary(i)(j) = auxiliary(j)(k) + 1;
//Get result
result = max_num(result, auxiliary(i)(j));
k += 1;
i -= 1;
}
}
while (i >= 0)
{
auxiliary(i)(j) = 2;
i -= 1;
}
j -= 1;
}
print("  " + result + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: ArithmeticProgression = new ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
var data1: Array[Int] = Array(-3, 0, 3, 7, 9, 12, 14, 15, 19, 21, 27);
var data2: Array[Int] = Array(8, 10, 12, 14, 17);
var data3: Array[Int] = Array(5, 8, 10, 12, 14, 16, 15);
var data4: Array[Int] = Array(1, 3, 5, 7, 9, 11, 13);
//Get the size of given data1
var size: Int = data1.length;
obj.length_of_longest_ap(data1, size);
//Get the size of given data2
size = data2.length;
obj.length_of_longest_ap(data2, size);
//Get the size of given data3
size = data3.length;
obj.length_of_longest_ap(data3, size);
//Get the size of given data4
size = data4.length;
obj.length_of_longest_ap(data4, size);
}
}``````

#### Output

`````` Element :  -3  0  3  7  9  12  14  15  19  21  27
Result :   6

Element :  8  10  12  14  17
Result :   4

Element :  5  8  10  12  14  16  15
Result :   5

Element :  1  3  5  7  9  11  13
Result :   7``````
``````// Swift program
// Find the length of longest arithmetic progression
// In sorted data
class ArithmeticProgression
{
//Display the elements of array
func print_data(_ data: [Int], _ size: Int)
{
print("\n Element :", terminator: "");
var i: Int = 0;
while (i < size)
{
print("  ", data[i], terminator: "");
i += 1;
}
}
//returns the maximum of given two numbers
func max_num(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
//When (a) is greater
return a;
}
//When b is greater than or equal to a
return b;
}
//returns the length of longest arithmetic progression
func length_of_longest_ap(_ data: [Int], _ size: Int)
{
//Display given element
self.print_data(data, size);
print("\n Result : ", terminator: "");
if (size <= 2)
{
//When have two or less than 2 elements
print("  ", size ,"\n", terminator: "");
return;
}
//Minimum 2 result are possible
var result: Int = 2;
//Create storage to calculate result
var auxiliary: [[Int]] = Array(repeating : Array( repeating:0 , count:size) ,  count:size);
//Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
//Set initial value of created storage
i = 0;
while (i < size)
{
// Set the [i] row and last column value is to 2
auxiliary[i][size - 1] = 2;
i += 1;
}
// Get last-1 position of given data
j = size - 2;
while (j >= 1)
{
k = j + 1;
i = j - 1;
while (i >= 0 && k <= size - 1)
{
if (data[i] + data[k] < 2 * data[j])
{
k += 1;
}
else if (data[i] + data[k] > 2 * data[j])
{
auxiliary[i][j] = 2;
i -= 1;
}
else
{
auxiliary[i][j] = auxiliary[j][k] + 1;
//Get result
result = self.max_num(result, auxiliary[i][j]);
k += 1;
i -= 1;
}
}
while (i >= 0)
{
auxiliary[i][j] = 2;
i -= 1;
}
j -= 1;
}
print("  ", result ,"\n", terminator: "");
}
}
func main()
{
let obj: ArithmeticProgression = ArithmeticProgression();
//Define the collection of sorted integer values
//This is test inputs
let data1: [Int] = [-3, 0, 3, 7, 9, 12, 14, 15, 19, 21, 27];
let data2: [Int] = [8, 10, 12, 14, 17];
let data3: [Int] = [5, 8, 10, 12, 14, 16, 15];
let data4: [Int] = [1, 3, 5, 7, 9, 11, 13];
//Get the size of given data1
var size: Int = data1.count;
obj.length_of_longest_ap(data1, size);
//Get the size of given data2
size = data2.count;
obj.length_of_longest_ap(data2, size);
//Get the size of given data3
size = data3.count;
obj.length_of_longest_ap(data3, size);
//Get the size of given data4
size = data4.count;
obj.length_of_longest_ap(data4, size);
}
main();``````

#### Output

`````` Element :   -3   0   3   7   9   12   14   15   19   21   27
Result :    6

Element :   8   10   12   14   17
Result :    4

Element :   5   8   10   12   14   16   15
Result :    5

Element :   1   3   5   7   9   11   13
Result :    7``````

## Time Complexity

The time complexity of this algorithm is approximately O(n^2), where n is the size of the input array. The nested loops for filling the `auxiliary` array contribute to this complexity.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.