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);
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);
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);
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)
{
// 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;
// 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;
//  Test C
//  arr = [ 12  11  10  7  8  1  2  9  3]
//  [1, 2, 3, 7, 8]
//  Result : 5
n = arr3.length;
}
}``````

#### 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()
{
// 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);
// 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);
//  Test C
//  arr = [ 12  11  10  7  8  1  2  9  3]
//  [1, 2, 3, 7, 8]
//  Result : 5
n = sizeof(arr3) / sizeof(arr3);
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)
{
// 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;
// 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;
//  Test C
//  arr = [ 12  11  10  7  8  1  2  9  3]
//  [1, 2, 3, 7, 8]
//  Result : 5
n = arr3.Length;
}
}``````

#### 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)
// 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)
//  Test C
//  arr = [ 12  11  10  7  8  1  2  9  3]
//  [1, 2, 3, 7, 8]
//  Result : 5
n = len(arr3)
}``````

#### 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()
{
// 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);
// 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);
//  Test C
//  arr = [ 12  11  10  7  8  1  2  9  3]
//  [1, 2, 3, 7, 8]
//  Result : 5
\$n = count(\$arr3);
}
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()
{
// 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;
// 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;
//  Test C
//  arr = [ 12  11  10  7  8  1  2  9  3]
//  [1, 2, 3, 7, 8]
//  Result : 5
n = arr3.length;
}
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 =  * (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 =  * (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() :
#  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)
#  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)
#   Test C
#   arr = [ 12  11  10  7  8  1  2  9  3]
#   [1, 2, 3, 7, 8]
#   Result : 5
n = len(arr3)

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()
#  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
#  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
#   Test C
#   arr = [ 12  11  10  7  8  1  2  9  3]
#   [1, 2, 3, 7, 8]
#   Result : 5
n = arr3.length
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;
// 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;
//  Test C
//  arr = [ 12  11  10  7  8  1  2  9  3]
//  [1, 2, 3, 7, 8]
//  Result : 5
n = arr3.length;
}
}``````

#### 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()
{
// 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;
// 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;
//  Test C
//  arr = [ 12  11  10  7  8  1  2  9  3]
//  [1, 2, 3, 7, 8]
//  Result : 5
n = arr3.count;
}
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
{
// 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();
// 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();
//  Test C
//  arr = [ 12  11  10  7  8  1  2  9  3]
//  [1, 2, 3, 7, 8]
//  Result : 5
n = arr3.count();
}``````

#### 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.

Categories
Relative Post