Skip to main content

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.

Last updated on by Kalkicode




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.

New Comment