Skip to main content

Find circular longest increasing subsequence

Here given code implementation process.

// C Program
// Find circular longest increasing subsequence
#include <stdio.h>

// Print the elements of given array
void printElement(int arr[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("  %d", arr[i]);
	}
}
int longestIncSubsequences(int arr[], int s, int e)
{
	// Define auxiliary array
	int length[e];
	// Define some auxiliary variables
	int i = 0;
	int j = 0;
	int ans = 1;
	// Set the initial value in auxiliary array
	for (i = 0; i < e; i++)
	{
		length[i] = 1;
	}
	// Execute loop through by size of array
	for (i = s + 1; i < e; i++)
	{
		// calculate increasing subsequence length
		for (j = s; j < i; j++)
		{
			if (arr[i] > arr[j])
			{
				if (length[j] + 1 > length[i])
				{
					length[i] = length[j] + 1;
					if (length[i] > ans)
					{
						ans = length[i];
					}
				}
			}
		}
	}
	return ans;
}
int maxValue(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	return b;
}
void longestSubsequences(int arr[], int n)
{
	if (n <= 0)
	{
		return;
	}
	int result = 0;
	int auxiliary[n *2];
	for (int i = 0; i < n; ++i)
	{
		auxiliary[i] = arr[i];
		auxiliary[i + n] = arr[i];
	}
	for (int i = 0; i < n; ++i)
	{
		result = maxValue(result, 
                          longestIncSubsequences(auxiliary, i, i + n));
	}
	// Display given array
	printElement(arr, n);
	// Display calculated result
	printf("\n Length of Longest increasing subsequence is : %d\n", result);
}
int main(int argc, char
	const *argv[])
{
	// Define array of integer elements
	int arr1[] = {
		7 , 8 , 6 , 9 , 4 , 5 , 6
	};
	int arr2[] = {
		7 , 9 , 3 , 4 , 8 , 7 , 2
	};
	int arr3[] = {
		12 , 11 , 10 , 7 , 8 , 1 , 2 , 9 , 3
	};
	// Test A
	// [ 7, 8, 6, 9, 4 , 5, 6]
	// length of Longest increasing subsequence 6
	// (4 , 5, 6, 7, 8, 9)
	//  Result = 6
	int n = sizeof(arr1) / sizeof(arr1[0]);
	longestSubsequences(arr1, n);
	// Test B
	// arr = [  7 , 9 , 3 , 4 , 8 , 7 , 2]
	// length of Longest increasing subsequence 4
	// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
	//  Result = 4
	n = sizeof(arr2) / sizeof(arr2[0]);
	longestSubsequences(arr2, n);
	//  Test C
	//  arr = [ 12  11  10  7  8  1  2  9  3]
	//  [1, 2, 3, 7, 8]
	//  Result : 5 
	n = sizeof(arr3) / sizeof(arr3[0]);
	longestSubsequences(arr3, n);
	return 0;
}

Output

  7  8  6  9  4  5  6
 Length of Longest increasing subsequence is : 6
  7  9  3  4  8  7  2
 Length of Longest increasing subsequence is : 4
  12  11  10  7  8  1  2  9  3
 Length of Longest increasing subsequence is : 5
// Java program for
// Find circular longest increasing subsequence
public class Subsequence
{
	// Print the elements of given array
	public void printElement(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + arr[i]);
		}
	}
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public int longestIncSubsequences(int[] arr, int s, int e)
	{
		// Define auxiliary array
		int[] length = new int[e];
		// Define some auxiliary variables
		int i = 0;
		int j = 0;
		int ans = 1;
		// Set the initial value in auxiliary array
		for (i = 0; i < e; i++)
		{
			length[i] = 1;
		}
		// Execute loop through by size of array
		for (i = s + 1; i < e; i++)
		{
			// calculate increasing subsequence length
			for (j = s; j < i; j++)
			{
				if (arr[i] > arr[j])
				{
					if (length[j] + 1 > length[i])
					{
						length[i] = length[j] + 1;
						if (length[i] > ans)
						{
							ans = length[i];
						}
					}
				}
			}
		}
		return ans;
	}
	// Handles the request to finding circular increasing subsequence
	public void findCireculLISS(int[] arr, int n)
	{
		if (n <= 0)
		{
			return;
		}
		int result = 0;
		// Auxiliary array which contains the double copy of original array
		int[] auxiliary = new int[n * 2];
		for (int i = 0; i < n; ++i)
		{
			auxiliary[i] = arr[i];
			// Append similar element at the end
			auxiliary[i + n] = arr[i];
		}
		for (int i = 0; i < n; ++i)
		{
			result = maxValue(result, 
                              longestIncSubsequences(auxiliary, i, i + n));
		}
		// Display given array
		printElement(arr, n);
		// Display calculated result
		System.out.println("\n Length of CLIS is : " + result);
	}
	public static void main(String[] args)
	{
		Subsequence task = new Subsequence();
		// Define array of integer elements
		int[] arr1 = {
			7 , 8 , 6 , 9 , 4 , 5 , 6
		};
		int[] arr2 = {
			7 , 9 , 3 , 4 , 8 , 7 , 2
		};
		int[] arr3 = {
			12 , 11 , 10 , 7 , 8 , 1 , 2 , 9 , 3
		};
		// Test A
		// [ 7, 8, 6, 9, 4 , 5, 6]
		// length of Longest circular increasing subsequence 6
		// (4 , 5, 6, 7, 8, 9)
		//  Result = 6
		int n = arr1.length;
		task.findCireculLISS(arr1, n);
		// Test B
		// arr = [  7 , 9 , 3 , 4 , 8 , 7 , 2]
		// length of Longest circular increasing subsequence 4
		// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
		//  Result = 4
		n = arr2.length;
		task.findCireculLISS(arr2, n);
		//  Test C
		//  arr = [ 12  11  10  7  8  1  2  9  3]
		//  [1, 2, 3, 7, 8]
		//  Result : 5 
		n = arr3.length;
		task.findCireculLISS(arr3, n);
	}
}

Output

 7 8 6 9 4 5 6
 Length of CLIS is : 6
 7 9 3 4 8 7 2
 Length of CLIS is : 4
 12 11 10 7 8 1 2 9 3
 Length of CLIS is : 5
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Find circular longest increasing subsequence
class Subsequence
{
	public:
		// Print the elements of given array
		void printElement(int arr[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				cout << " " << arr[i];
			}
		}
	int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	int longestIncSubsequences(int arr[], int s, int e)
	{
		// Define auxiliary array
		int length[e];
		// Define some auxiliary variables
		int i = 0;
		int j = 0;
		int ans = 1;
		// Set the initial value in auxiliary array
		for (i = 0; i < e; i++)
		{
			length[i] = 1;
		}
		// Execute loop through by size of array
		for (i = s + 1; i < e; i++)
		{
			// calculate increasing subsequence length
			for (j = s; j < i; j++)
			{
				if (arr[i] > arr[j])
				{
					if (length[j] + 1 > length[i])
					{
						length[i] = length[j] + 1;
						if (length[i] > ans)
						{
							ans = length[i];
						}
					}
				}
			}
		}
		return ans;
	}
	// Handles the request to finding circular increasing subsequence
	void findCireculLISS(int arr[], int n)
	{
		if (n <= 0)
		{
			return;
		}
		int result = 0;
		// Auxiliary array which contains the double copy of original array
		int auxiliary[n *2];
		for (int i = 0; i < n; ++i)
		{
			auxiliary[i] = arr[i];
			// Append similar element at the end
			auxiliary[i + n] = arr[i];
		}
		for (int i = 0; i < n; ++i)
		{
			result = this->maxValue(result, 
                                    this->longestIncSubsequences(
              auxiliary, i, i + n));
		}
		// Display given array
		this->printElement(arr, n);
		// Display calculated result
		cout << "\n Length of CLIS is : " << result << endl;
	}
};
int main()
{
	Subsequence *task = new Subsequence();
	// Define array of integer elements
	int arr1[] = {
		7 , 8 , 6 , 9 , 4 , 5 , 6
	};
	int arr2[] = {
		7 , 9 , 3 , 4 , 8 , 7 , 2
	};
	int arr3[] = {
		12 , 11 , 10 , 7 , 8 , 1 , 2 , 9 , 3
	};
	// Test A
	// [ 7, 8, 6, 9, 4 , 5, 6]
	// length of Longest circular increasing subsequence 6
	// (4 , 5, 6, 7, 8, 9)
	//  Result = 6
	int n = sizeof(arr1) / sizeof(arr1[0]);
	task->findCireculLISS(arr1, n);
	// Test B
	// arr = [  7 , 9 , 3 , 4 , 8 , 7 , 2]
	// length of Longest circular increasing subsequence 4
	// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
	//  Result = 4
	n = sizeof(arr2) / sizeof(arr2[0]);
	task->findCireculLISS(arr2, n);
	//  Test C
	//  arr = [ 12  11  10  7  8  1  2  9  3]
	//  [1, 2, 3, 7, 8]
	//  Result : 5 
	n = sizeof(arr3) / sizeof(arr3[0]);
	task->findCireculLISS(arr3, n);
	return 0;
}

Output

 7 8 6 9 4 5 6
 Length of CLIS is : 6
 7 9 3 4 8 7 2
 Length of CLIS is : 4
 12 11 10 7 8 1 2 9 3
 Length of CLIS is : 5
// Include namespace system
using System;
// Csharp program for
// Find circular longest increasing subsequence
public class Subsequence
{
	// Print the elements of given array
	public void printElement(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
	}
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public int longestIncSubsequences(int[] arr, int s, int e)
	{
		// Define auxiliary array
		int[] length = new int[e];
		// Define some auxiliary variables
		int i = 0;
		int j = 0;
		int ans = 1;
		// Set the initial value in auxiliary array
		for (i = 0; i < e; i++)
		{
			length[i] = 1;
		}
		// Execute loop through by size of array
		for (i = s + 1; i < e; i++)
		{
			// calculate increasing subsequence length
			for (j = s; j < i; j++)
			{
				if (arr[i] > arr[j])
				{
					if (length[j] + 1 > length[i])
					{
						length[i] = length[j] + 1;
						if (length[i] > ans)
						{
							ans = length[i];
						}
					}
				}
			}
		}
		return ans;
	}
	// Handles the request to finding circular increasing subsequence
	public void findCireculLISS(int[] arr, int n)
	{
		if (n <= 0)
		{
			return;
		}
		int result = 0;
		// Auxiliary array which contains the double copy of original array
		int[] auxiliary = new int[n * 2];
		for (int i = 0; i < n; ++i)
		{
			auxiliary[i] = arr[i];
			// Append similar element at the end
			auxiliary[i + n] = arr[i];
		}
		for (int i = 0; i < n; ++i)
		{
			result = this.maxValue(result, 
                                   this.longestIncSubsequences(
              auxiliary, i, i + n));
		}
		// Display given array
		this.printElement(arr, n);
		// Display calculated result
		Console.WriteLine("\n Length of CLIS is : " + result);
	}
	public static void Main(String[] args)
	{
		Subsequence task = new Subsequence();
		// Define array of integer elements
		int[] arr1 = {
			7 , 8 , 6 , 9 , 4 , 5 , 6
		};
		int[] arr2 = {
			7 , 9 , 3 , 4 , 8 , 7 , 2
		};
		int[] arr3 = {
			12 , 11 , 10 , 7 , 8 , 1 , 2 , 9 , 3
		};
		// Test A
		// [ 7, 8, 6, 9, 4 , 5, 6]
		// length of Longest circular increasing subsequence 6
		// (4 , 5, 6, 7, 8, 9)
		//  Result = 6
		int n = arr1.Length;
		task.findCireculLISS(arr1, n);
		// Test B
		// arr = [  7 , 9 , 3 , 4 , 8 , 7 , 2]
		// length of Longest circular increasing subsequence 4
		// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
		//  Result = 4
		n = arr2.Length;
		task.findCireculLISS(arr2, n);
		//  Test C
		//  arr = [ 12  11  10  7  8  1  2  9  3]
		//  [1, 2, 3, 7, 8]
		//  Result : 5 
		n = arr3.Length;
		task.findCireculLISS(arr3, n);
	}
}

Output

 7 8 6 9 4 5 6
 Length of CLIS is : 6
 7 9 3 4 8 7 2
 Length of CLIS is : 4
 12 11 10 7 8 1 2 9 3
 Length of CLIS is : 5
package main
import "fmt"
// Go program for
// Find circular longest increasing subsequence
type Subsequence struct {}
func getSubsequence() * Subsequence {
	var me *Subsequence = &Subsequence {}
	return me
}
// Print the elements of given array
func(this Subsequence) printElement(arr[] int, n int) {
	for i := 0 ; i < n ; i++ {
		fmt.Print(" ", arr[i])
	}
}
func(this Subsequence) maxValue(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func(this Subsequence) longestIncSubsequences(arr[] int, 
	s int, e int) int {
	// Define auxiliary array
	var length = make([] int, e)
	// Define some auxiliary variables
	var i int = 0
	var j int = 0
	var ans int = 1
	// Set the initial value in auxiliary array
	for i = 0 ; i < e ; i++ {
		length[i] = 1
	}
	// Execute loop through by size of array
	for i = s + 1 ; i < e ; i++ {
		// calculate increasing subsequence length
		for j = s ; j < i ; j++ {
			if arr[i] > arr[j] {
				if length[j] + 1 > length[i] {
					length[i] = length[j] + 1
					if length[i] > ans {
						ans = length[i]
					}
				}
			}
		}
	}
	return ans
}
// Handles the request to finding circular increasing subsequence
func(this Subsequence) findCireculLISS(arr[] int, n int) {
	if n <= 0 {
		return
	}
	var result int = 0
	// Auxiliary array which contains the double copy of original array
	var auxiliary = make([] int, n * 2)
	for i := 0 ; i < n ; i++ {
		auxiliary[i] = arr[i]
		// Append similar element at the end
		auxiliary[i + n] = arr[i]
	}
	for i := 0 ; i < n ; i++ {
		result = this.maxValue(result, 
			this.longestIncSubsequences(auxiliary, i, i + n))
	}
	// Display given array
	this.printElement(arr, n)
	// Display calculated result
	fmt.Println("\n Length of CLIS is : ", result)
}
func main() {
	var task * Subsequence = getSubsequence()
	// Define array of integer elements
	var arr1 = [] int {
		7,
		8,
		6,
		9,
		4,
		5,
		6,
	}
	var arr2 = [] int {
		7,
		9,
		3,
		4,
		8,
		7,
		2,
	}
	var arr3 = [] int {
		12,
		11,
		10,
		7,
		8,
		1,
		2,
		9,
		3,
	}
	// Test A
	// [ 7, 8, 6, 9, 4 , 5, 6]
	// length of Longest circular increasing subsequence 6
	// (4 , 5, 6, 7, 8, 9)
	//  Result = 6
	var n int = len(arr1)
	task.findCireculLISS(arr1, n)
	// Test B
	// arr = [  7 , 9 , 3 , 4 , 8 , 7 , 2]
	// length of Longest circular increasing subsequence 4
	// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
	//  Result = 4
	n = len(arr2)
	task.findCireculLISS(arr2, n)
	//  Test C
	//  arr = [ 12  11  10  7  8  1  2  9  3]
	//  [1, 2, 3, 7, 8]
	//  Result : 5 
	n = len(arr3)
	task.findCireculLISS(arr3, n)
}

Output

 7 8 6 9 4 5 6
 Length of CLIS is : 6
 7 9 3 4 8 7 2
 Length of CLIS is : 4
 12 11 10 7 8 1 2 9 3
 Length of CLIS is : 5
<?php
// Php program for
// Find circular longest increasing subsequence
class Subsequence
{
	// Print the elements of given array
	public	function printElement($arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo(" ".$arr[$i]);
		}
	}
	public	function maxValue($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		return $b;
	}
	public	function longestIncSubsequences($arr, $s, $e)
	{
		//  Define auxiliary list
		//  Set initial 1 length of each element
		$length = array_fill(0, $e, 1);
		// Define some auxiliary variables
		$i = 0;
		$j = 0;
		$ans = 1;
		// Execute loop through by size of array
		for ($i = $s + 1; $i < $e; $i++)
		{
			// calculate increasing subsequence length
			for ($j = $s; $j < $i; $j++)
			{
				if ($arr[$i] > $arr[$j])
				{
					if ($length[$j] + 1 > $length[$i])
					{
						$length[$i] = $length[$j] + 1;
						if ($length[$i] > $ans)
						{
							$ans = $length[$i];
						}
					}
				}
			}
		}
		return $ans;
	}
	// Handles the request to finding circular increasing subsequence
	public	function findCireculLISS($arr, $n)
	{
		if ($n <= 0)
		{
			return;
		}
		$result = 0;
		// Auxiliary array which contains the double copy of original array
		$auxiliary = array_fill(0, $n * 2, 0);
		for ($i = 0; $i < $n; ++$i)
		{
			$auxiliary[$i] = $arr[$i];
			// Append similar element at the end
			$auxiliary[$i + $n] = $arr[$i];
		}
		for ($i = 0; $i < $n; ++$i)
		{
			$result = $this->maxValue($result, 
                     $this->longestIncSubsequences($auxiliary, 
                                                   $i, $i + $n));
		}
		// Display given array
		$this->printElement($arr, $n);
		// Display calculated result
		echo("\n Length of CLIS is : ".$result.
			"\n");
	}
}

function main()
{
	$task = new Subsequence();
	// Define array of integer elements
	$arr1 = array(7, 8, 6, 9, 4, 5, 6);
	$arr2 = array(7, 9, 3, 4, 8, 7, 2);
	$arr3 = array(12, 11, 10, 7, 8, 1, 2, 9, 3);
	// Test A
	// [ 7, 8, 6, 9, 4 , 5, 6]
	// length of Longest circular increasing subsequence 6
	// (4 , 5, 6, 7, 8, 9)
	//  Result = 6
	$n = count($arr1);
	$task->findCireculLISS($arr1, $n);
	// Test B
	// arr = [  7 , 9 , 3 , 4 , 8 , 7 , 2]
	// length of Longest circular increasing subsequence 4
	// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
	//  Result = 4
	$n = count($arr2);
	$task->findCireculLISS($arr2, $n);
	//  Test C
	//  arr = [ 12  11  10  7  8  1  2  9  3]
	//  [1, 2, 3, 7, 8]
	//  Result : 5
	$n = count($arr3);
	$task->findCireculLISS($arr3, $n);
}
main();

Output

 7 8 6 9 4 5 6
 Length of CLIS is : 6
 7 9 3 4 8 7 2
 Length of CLIS is : 4
 12 11 10 7 8 1 2 9 3
 Length of CLIS is : 5
// Node JS program for
// Find circular longest increasing subsequence
class Subsequence
{
	// Print the elements of given array
	printElement(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
	}
	maxValue(a, b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	longestIncSubsequences(arr, s, e)
	{
		//  Define auxiliary list
		//  Set initial 1 length of each element
		var length = Array(e).fill(1);
		// Define some auxiliary variables
		var i = 0;
		var j = 0;
		var ans = 1;
		// Execute loop through by size of array
		for (i = s + 1; i < e; i++)
		{
			// calculate increasing subsequence length
			for (j = s; j < i; j++)
			{
				if (arr[i] > arr[j])
				{
					if (length[j] + 1 > length[i])
					{
						length[i] = length[j] + 1;
						if (length[i] > ans)
						{
							ans = length[i];
						}
					}
				}
			}
		}
		return ans;
	}
	// Handles the request to finding circular increasing subsequence
	findCireculLISS(arr, n)
	{
		if (n <= 0)
		{
			return;
		}
		var result = 0;
		// Auxiliary array which contains the double copy of original array
		var auxiliary = Array(n * 2).fill(0);
		for (var i = 0; i < n; ++i)
		{
			auxiliary[i] = arr[i];
			// Append similar element at the end
			auxiliary[i + n] = arr[i];
		}
		for (var i = 0; i < n; ++i)
		{
			result = this.maxValue(result, this.longestIncSubsequences(auxiliary, i, i + n));
		}
		// Display given array
		this.printElement(arr, n);
		// Display calculated result
		console.log("\n Length of CLIS is : " + result);
	}
}

function main()
{
	var task = new Subsequence();
	// Define array of integer elements
	var arr1 = [7, 8, 6, 9, 4, 5, 6];
	var arr2 = [7, 9, 3, 4, 8, 7, 2];
	var arr3 = [12, 11, 10, 7, 8, 1, 2, 9, 3];
	// Test A
	// [ 7, 8, 6, 9, 4 , 5, 6]
	// length of Longest circular increasing subsequence 6
	// (4 , 5, 6, 7, 8, 9)
	//  Result = 6
	var n = arr1.length;
	task.findCireculLISS(arr1, n);
	// Test B
	// arr = [  7 , 9 , 3 , 4 , 8 , 7 , 2]
	// length of Longest circular increasing subsequence 4
	// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
	//  Result = 4
	n = arr2.length;
	task.findCireculLISS(arr2, n);
	//  Test C
	//  arr = [ 12  11  10  7  8  1  2  9  3]
	//  [1, 2, 3, 7, 8]
	//  Result : 5
	n = arr3.length;
	task.findCireculLISS(arr3, n);
}
main();

Output

 7 8 6 9 4 5 6
 Length of CLIS is : 6
 7 9 3 4 8 7 2
 Length of CLIS is : 4
 12 11 10 7 8 1 2 9 3
 Length of CLIS is : 5
#  Python 3 program for
#  Find circular longest increasing subsequence
class Subsequence :
	#  Print the elements of given list
	def printElement(self, arr, n) :
		i = 0
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
	
	def maxValue(self, a, b) :
		if (a > b) :
			return a
		
		return b
	
	def longestIncSubsequences(self, arr, s, e) :
		#   Define auxiliary list
		#   Set initial 1 length of each element
		length = [1] * (e)
		#  Define some auxiliary variables
		i = 0
		j = 0
		ans = 1
		i = s + 1
		#  Execute loop through by size of list
		while (i < e) :
			j = s
			#  calculate increasing subsequence length
			while (j < i) :
				if (arr[i] > arr[j]) :
					if (length[j] + 1 > length[i]) :
						length[i] = length[j] + 1
						if (length[i] > ans) :
							ans = length[i]
						
					
				
				j += 1
			
			i += 1
		
		return ans
	
	#  Handles the request to finding circular increasing subsequence
	def findCireculLISS(self, arr, n) :
		if (n <= 0) :
			return
		
		result = 0
		#  Auxiliary list which contains the double copy of original list
		auxiliary = [0] * (n * 2)
		i = 0
		while (i < n) :
			auxiliary[i] = arr[i]
			#  Append similar element at the end
			auxiliary[i + n] = arr[i]
			i += 1
		
		i = 0
		while (i < n) :
			result = self.maxValue(result, self.longestIncSubsequences(auxiliary, i, i + n))
			i += 1
		
		#  Display given list
		self.printElement(arr, n)
		#  Display calculated result
		print("\n Length of CLIS is : ", result)
	

def main() :
	task = Subsequence()
	#  Define list of integer elements
	arr1 = [7, 8, 6, 9, 4, 5, 6]
	arr2 = [7, 9, 3, 4, 8, 7, 2]
	arr3 = [12, 11, 10, 7, 8, 1, 2, 9, 3]
	#  Test A
	#  [ 7, 8, 6, 9, 4 , 5, 6]
	#  length of Longest circular increasing subsequence 6
	#  (4 , 5, 6, 7, 8, 9)
	#   Result = 6
	n = len(arr1)
	task.findCireculLISS(arr1, n)
	#  Test B
	#  arr = [  7 , 9 , 3 , 4 , 8 , 7 , 2]
	#  length of Longest circular increasing subsequence 4
	#  (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
	#   Result = 4
	n = len(arr2)
	task.findCireculLISS(arr2, n)
	#   Test C
	#   arr = [ 12  11  10  7  8  1  2  9  3]
	#   [1, 2, 3, 7, 8]
	#   Result : 5
	n = len(arr3)
	task.findCireculLISS(arr3, n)

if __name__ == "__main__": main()

Output

  7  8  6  9  4  5  6
 Length of CLIS is :  6
  7  9  3  4  8  7  2
 Length of CLIS is :  4
  12  11  10  7  8  1  2  9  3
 Length of CLIS is :  5
#  Ruby program for
#  Find circular longest increasing subsequence
class Subsequence 
	#  Print the elements of given array
	def printElement(arr, n) 
		i = 0
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

	end

	def maxValue(a, b) 
		if (a > b) 
			return a
		end

		return b
	end

	def longestIncSubsequences(arr, s, e) 
		#   Define auxiliary list
		#   Set initial 1 length of each element
		length = Array.new(e) {1}
		#  Define some auxiliary variables
		i = 0
		j = 0
		ans = 1
		i = s + 1
		#  Execute loop through by size of array
		while (i < e) 
			j = s
			#  calculate increasing subsequence length
			while (j < i) 
				if (arr[i] > arr[j]) 
					if (length[j] + 1 > length[i]) 
						length[i] = length[j] + 1
						if (length[i] > ans) 
							ans = length[i]
						end

					end

				end

				j += 1
			end

			i += 1
		end

		return ans
	end

	#  Handles the request to finding circular increasing subsequence
	def findCireculLISS(arr, n) 
		if (n <= 0) 
			return
		end

		result = 0
		#  Auxiliary array which contains the double copy of original array
		auxiliary = Array.new(n * 2) {0}
		i = 0
		while (i < n) 
			auxiliary[i] = arr[i]
			#  Append similar element at the end
			auxiliary[i + n] = arr[i]
			i += 1
		end

		i = 0
		while (i < n) 
			result = self.maxValue(result,
                     self.longestIncSubsequences(auxiliary, i, i + n))
			i += 1
		end

		#  Display given array
		self.printElement(arr, n)
		#  Display calculated result
		print("\n Length of CLIS is : ", result, "\n")
	end

end

def main() 
	task = Subsequence.new()
	#  Define array of integer elements
	arr1 = [7, 8, 6, 9, 4, 5, 6]
	arr2 = [7, 9, 3, 4, 8, 7, 2]
	arr3 = [12, 11, 10, 7, 8, 1, 2, 9, 3]
	#  Test A
	#  [ 7, 8, 6, 9, 4 , 5, 6]
	#  length of Longest circular increasing subsequence 6
	#  (4 , 5, 6, 7, 8, 9)
	#   Result = 6
	n = arr1.length
	task.findCireculLISS(arr1, n)
	#  Test B
	#  arr = [  7 , 9 , 3 , 4 , 8 , 7 , 2]
	#  length of Longest circular increasing subsequence 4
	#  (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
	#   Result = 4
	n = arr2.length
	task.findCireculLISS(arr2, n)
	#   Test C
	#   arr = [ 12  11  10  7  8  1  2  9  3]
	#   [1, 2, 3, 7, 8]
	#   Result : 5
	n = arr3.length
	task.findCireculLISS(arr3, n)
end

main()

Output

 7 8 6 9 4 5 6
 Length of CLIS is : 6
 7 9 3 4 8 7 2
 Length of CLIS is : 4
 12 11 10 7 8 1 2 9 3
 Length of CLIS is : 5

// Scala program for
// Find circular longest increasing subsequence
class Subsequence()
{
	// Print the elements of given array
	def printElement(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
	}
	def maxValue(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		return b;
	}
	def longestIncSubsequences(arr: Array[Int], s: Int, e: Int): Int = {
		//  Define auxiliary list
		//  Set initial 1 length of each element
		var length: Array[Int] = Array.fill[Int](e)(1);
		// Define some auxiliary variables
		var i: Int = s + 1;
		var j: Int = 0;
		var ans: Int = 1;
		// Execute loop through by size of array
		while (i < e)
		{
			j = s;
			// calculate increasing subsequence length
			while (j < i)
			{
				if (arr(i) > arr(j))
				{
					if (length(j) + 1 > length(i))
					{
						length(i) = length(j) + 1;
						if (length(i) > ans)
						{
							ans = length(i);
						}
					}
				}
				j += 1;
			}
			i += 1;
		}
		return ans;
	}
	// Handles the request to finding circular increasing subsequence
	def findCireculLISS(arr: Array[Int], n: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		var result: Int = 0;
		// Auxiliary array which contains the double copy of original array
		var auxiliary: Array[Int] = Array.fill[Int](n * 2)(0);
		var i: Int = 0;
		while (i < n)
		{
			auxiliary(i) = arr(i);
			// Append similar element at the end
			auxiliary(i + n) = arr(i);
			i += 1;
		}
		i = 0;
		while (i < n)
		{
			result = maxValue(result, 
                      longestIncSubsequences(auxiliary, i, i + n));
			i += 1;
		}
		// Display given array
		printElement(arr, n);
		// Display calculated result
		println("\n Length of CLIS is : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subsequence = new Subsequence();
		// Define array of integer elements
		var arr1: Array[Int] = Array(7, 8, 6, 9, 4, 5, 6);
		var arr2: Array[Int] = Array(7, 9, 3, 4, 8, 7, 2);
		var arr3: Array[Int] = Array(12, 11, 10, 7, 8, 1, 2, 9, 3);
		// Test A
		// [ 7, 8, 6, 9, 4 , 5, 6]
		// length of Longest circular increasing subsequence 6
		// (4 , 5, 6, 7, 8, 9)
		//  Result = 6
		var n: Int = arr1.length;
		task.findCireculLISS(arr1, n);
		// Test B
		// arr = [  7 , 9 , 3 , 4 , 8 , 7 , 2]
		// length of Longest circular increasing subsequence 4
		// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
		//  Result = 4
		n = arr2.length;
		task.findCireculLISS(arr2, n);
		//  Test C
		//  arr = [ 12  11  10  7  8  1  2  9  3]
		//  [1, 2, 3, 7, 8]
		//  Result : 5
		n = arr3.length;
		task.findCireculLISS(arr3, n);
	}
}

Output

 7 8 6 9 4 5 6
 Length of CLIS is : 6
 7 9 3 4 8 7 2
 Length of CLIS is : 4
 12 11 10 7 8 1 2 9 3
 Length of CLIS is : 5
import Foundation;
// Swift 4 program for
// Find circular longest increasing subsequence
class Subsequence
{
	// Print the elements of given array
	func printElement(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
	}
	func maxValue(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	func longestIncSubsequences(_ arr: [Int], _ s: Int, _ e: Int) -> Int
	{
		//  Define auxiliary list
		//  Set initial 1 length of each element
		var length: [Int] = Array(repeating: 1, count: e);
		// Define some auxiliary variables
		var i: Int = s + 1;
		var j: Int = 0;
		var ans: Int = 1;
	
		// Execute loop through by size of array
		while (i < e)
		{
			j = s;
			// calculate increasing subsequence length
			while (j < i)
			{
				if (arr[i] > arr[j])
				{
					if (length[j] + 1 > length[i])
					{
						length[i] = length[j] + 1;
						if (length[i] > ans)
						{
							ans = length[i];
						}
					}
				}
				j += 1;
			}
			i += 1;
		}
		return ans;
	}
	// Handles the request to finding circular increasing subsequence
	func findCireculLISS(_ arr: [Int], _ n: Int)
	{
		if (n <= 0)
		{
			return;
		}
		var result: Int = 0;
		// Auxiliary array which contains the double copy of original array
		var auxiliary: [Int] = Array(repeating: 0, count: n * 2);
		var i: Int = 0;
		while (i < n)
		{
			auxiliary[i] = arr[i];
			// Append similar element at the end
			auxiliary[i + n] = arr[i];
			i += 1;
		}
		i = 0;
		while (i < n)
		{
			result = self.maxValue(result, 
                     self.longestIncSubsequences(auxiliary, i, i + n));
			i += 1;
		}
		// Display given array
		self.printElement(arr, n);
		// Display calculated result
		print("\n Length of CLIS is : ", result);
	}
}
func main()
{
	let task: Subsequence = Subsequence();
	// Define array of integer elements
	let arr1: [Int] = [7, 8, 6, 9, 4, 5, 6];
	let arr2: [Int] = [7, 9, 3, 4, 8, 7, 2];
	let arr3: [Int] = [12, 11, 10, 7, 8, 1, 2, 9, 3];
	// Test A
	// [ 7, 8, 6, 9, 4 , 5, 6]
	// length of Longest circular increasing subsequence 6
	// (4 , 5, 6, 7, 8, 9)
	//  Result = 6
	var n: Int = arr1.count;
	task.findCireculLISS(arr1, n);
	// Test B
	// arr = [  7 , 9 , 3 , 4 , 8 , 7 , 2]
	// length of Longest circular increasing subsequence 4
	// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
	//  Result = 4
	n = arr2.count;
	task.findCireculLISS(arr2, n);
	//  Test C
	//  arr = [ 12  11  10  7  8  1  2  9  3]
	//  [1, 2, 3, 7, 8]
	//  Result : 5
	n = arr3.count;
	task.findCireculLISS(arr3, n);
}
main();

Output

  7  8  6  9  4  5  6
 Length of CLIS is :  6
  7  9  3  4  8  7  2
 Length of CLIS is :  4
  12  11  10  7  8  1  2  9  3
 Length of CLIS is :  5
// Kotlin program for
// Find circular longest increasing subsequence
class Subsequence
{
	// Print the elements of given array
	fun printElement(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr[i]);
			i += 1;
		}
	}
	fun maxValue(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	fun longestIncSubsequences(arr: Array < Int > , s: Int, e: Int): Int
	{
		//  Define auxiliary list
		//  Set initial 1 length of each element
		val length: Array < Int > = Array(e)
		{
			1
		};
		// Define some auxiliary variables
		var i: Int = s + 1;
		var j: Int;
		var ans: Int = 1;

		// Execute loop through by size of array
		while (i < e)
		{
			j = s;
			// calculate increasing subsequence length
			while (j < i)
			{
				if (arr[i] > arr[j])
				{
					if (length[j] + 1 > length[i])
					{
						length[i] = length[j] + 1;
						if (length[i] > ans)
						{
							ans = length[i];
						}
					}
				}
				j += 1;
			}
			i += 1;
		}
		return ans;
	}
	// Handles the request to finding circular increasing subsequence
	fun findCireculLISS(arr: Array < Int > , n: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		var result: Int = 0;
		// Auxiliary array which contains the double copy of original array
		val auxiliary: Array < Int > = Array(n * 2)
		{
			1
		};
		var i: Int = 0;
		while (i < n)
		{
			auxiliary[i] = arr[i];
			// Append similar element at the end
			auxiliary[i + n] = arr[i];
			i += 1;
		}
		i = 0;
		while (i < n)
		{
			result = this.maxValue(result, 
                     this.longestIncSubsequences(
              auxiliary, i, i + n));
			i += 1;
		}
		// Display given array
		this.printElement(arr, n);
		// Display calculated result
		println("\n Length of CLIS is : " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subsequence = Subsequence();
	// Define array of integer elements
	val arr1: Array < Int > = arrayOf(7, 8, 6, 9, 4, 5, 6);
	val arr2: Array < Int > = arrayOf(7, 9, 3, 4, 8, 7, 2);
	val arr3: Array < Int > = arrayOf(12, 11, 10, 7, 8, 1, 2, 9, 3);
	// Test A
	// [ 7, 8, 6, 9, 4 , 5, 6]
	// length of Longest circular increasing subsequence 6
	// (4 , 5, 6, 7, 8, 9)
	//  Result = 6
	var n: Int = arr1.count();
	task.findCireculLISS(arr1, n);
	// Test B
	// arr = [  7 , 9 , 3 , 4 , 8 , 7 , 2]
	// length of Longest circular increasing subsequence 4
	// (3, 4, 7 , 9), (3 , 4 , 8, 9) etc
	//  Result = 4
	n = arr2.count();
	task.findCireculLISS(arr2, n);
	//  Test C
	//  arr = [ 12  11  10  7  8  1  2  9  3]
	//  [1, 2, 3, 7, 8]
	//  Result : 5
	n = arr3.count();
	task.findCireculLISS(arr3, n);
}

Output

 7 8 6 9 4 5 6
 Length of CLIS is : 6
 7 9 3 4 8 7 2
 Length of CLIS is : 4
 12 11 10 7 8 1 2 9 3
 Length of CLIS is : 5
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