Skip to main content

Find the length of longest arithmetic progression

Here given code implementation process.

// 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
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