Posted on by Kalkicode
Code Dynamic Programming

Find circular longest increasing subsequence

In this article, we will explore the problem of finding the longest increasing subsequence in a circular array. We will provide a detailed explanation of the problem statement and present a C code implementation to solve it. The code utilizes dynamic programming concepts to find the solution efficiently. The article will break down the problem, explain the solution approach, and discuss the code implementation.

Problem Statement:

Problem Statement: Given a circular array of integers, we need to find the longest increasing subsequence in the array. A subsequence is a sequence of elements taken from the array, maintaining their relative order, but not necessarily consecutive. An increasing subsequence is one where each element is greater than its preceding element. The circular array wraps around, meaning that the next element after the last element is the first element in the array.

Code Solution:

To solve this problem, we employ a dynamic programming approach. The main idea is to consider every possible starting point in the array and calculate the length of the longest increasing subsequence from that point. We keep track of the maximum length encountered so far and return it as the final result.

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

Code Explanation:

The provided C code consists of several functions that work together to find the solution. Let's go through each function and understand its purpose:

  1. printElement(int arr[], int n): This function simply prints the elements of the given array.

  2. longestIncSubsequences(int arr[], int s, int e): This function calculates the length of the longest increasing subsequence within a given range of indices (s to e) in the array. It utilizes an auxiliary array called length to store the lengths of increasing subsequences ending at each index. The function iterates through the array, comparing elements and updating the lengths accordingly. It returns the maximum length found.

  3. maxValue(int a, int b): This function returns the maximum value between two integers.

  4. longestSubsequences(int arr[], int n): This function finds the longest increasing subsequence in a circular array. It takes the input array and its size as parameters. The function creates an auxiliary array auxiliary by duplicating the input array. It then iterates through each starting index in the original array, calling longestIncSubsequences to calculate the length of the longest increasing subsequence starting from that index. It keeps track of the maximum length encountered and prints the input array along with the result.

  5. main(int argc, char const *argv[]): The main function serves as the entry point of the program. It defines three test arrays and calls the longestSubsequences function for each array, displaying the input array and the length of the longest increasing subsequence.

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





Categories
Relative Post