Given an array, the task is to find LIS (Longest Increasing Subsequence) in a circular way.
Examples :
Input : arr[] = {5, 4, 3, 2, 1}
Output : 2
Although there is no LIS in a given array
but in a circular form there can be
{1, 5}, {2, 5}, ......
Input : arr[]= {5, 6, 7, 1, 2, 3}
Output : 6
{1, 2, 3, 5, 6, 7} will be the LIS in the
circular manner.
- Append the same elements(i.e. whole array) with the given array.
- For every window of size n(no. of elements in the given array), perform LIS.
- Return maximum length.
For example : Given array is {1, 4, 6, 2, 3}
After appending elements resultant array
will be {1, 4, 6, 2, 3, 1, 4, 6, 2, 3}.
Now for every consecutive n elements perform LIS.
1- {1, 4, 6, 2, 3} --3 is length of LIS.
2- {4, 6, 2, 3, 1} --2 is length of LIS.
3- {6, 2, 3, 1, 4} --3
4- {2, 3, 1, 4, 6}-- 4 {2, 3, 4, 6}
5- {3, 1, 4, 6, 2} --3.
6- {1, 4, 6, 2, 3} Original list.
So, maximum length of LIS in circular manner is 4.
As in the last window we will have the same elements as in the given array which we don’t need to compute again, so we can append only n-1 elements to reduce the number of operations.
C++
// C++ implementation to find LIS in circular way#include <bits/stdc++.h>using namespace std;// Utility function to find LIS using Dynamic programmingint computeLIS(int circBuff[], int start, int end, int n){ int LIS[end - start]; /* Initialize LIS values for all indexes */ for (int i = start; i < end; i++) LIS[i] = 1; /* Compute optimized LIS values in bottom up manner */ for (int i = start + 1; i < end; i++) // Set j on the basis of current window // i.e. first element of the current window for (int j = start; j < i; j++) if (circBuff[i] > circBuff[j] && LIS[i] < LIS[j] + 1) LIS[i] = LIS[j] + 1; /* Pick maximum of all LIS values */ int res = INT_MIN; for (int i = start; i < end; i++) res = max(res, LIS[i]); return res;}// Function to find Longest Increasing subsequence in// Circular mannerint LICS(int arr[], int n){ // Make a copy of given array by appending same // array elements to itself int circBuff[2 * n]; for (int i = 0; i < n; i++) circBuff[i] = arr[i]; for (int i = n; i < 2 * n; i++) circBuff[i] = arr[i - n]; // Perform LIS for each window of size n int res = INT_MIN; for (int i = 0; i < n; i++) res = max(computeLIS(circBuff, i, i + n, n), res); return res;}/* Driver program to test above function */int main(){ int arr[] = { 1, 4, 6, 2, 3 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Length of LICS is " << LICS(arr, n); return 0;} |
C
// C implementation to find LIS in circular way#include <limits.h>#include <stdio.h>// Find maximum between two numbers.int max(int num1, int num2){ return (num1 > num2) ? num1 : num2;}// Utility function to find LIS using Dynamic programmingint computeLIS(int circBuff[], int start, int end, int n){ int LIS[end - start]; /* Initialize LIS values for all indexes */ for (int i = start; i < end; i++) LIS[i] = 1; /* Compute optimized LIS values in bottom up manner */ for (int i = start + 1; i < end; i++) // Set j on the basis of current window // i.e. first element of the current window for (int j = start; j < i; j++) if (circBuff[i] > circBuff[j] && LIS[i] < LIS[j] + 1) LIS[i] = LIS[j] + 1; /* Pick maximum of all LIS values */ int res = INT_MIN; for (int i = start; i < end; i++) res = max(res, LIS[i]); return res;}// Function to find Longest Increasing subsequence in// Circular mannerint LICS(int arr[], int n){ // Make a copy of given array by appending same // array elements to itself int circBuff[2 * n]; for (int i = 0; i < n; i++) circBuff[i] = arr[i]; for (int i = n; i < 2 * n; i++) circBuff[i] = arr[i - n]; // Perform LIS for each window of size n int res = INT_MIN; for (int i = 0; i < n; i++) res = max(computeLIS(circBuff, i, i + n, n), res); return res;}/* Driver program to test above function */int main(){ int arr[] = { 1, 4, 6, 2, 3 }; int n = sizeof(arr) / sizeof(arr[0]); printf("Length of LICS is %d ", LICS(arr, n)); return 0;}// This code is contributed by Sania Kumari Gupta |
Java
// Java implementation to find LIS in circular wayclass Test{ // Utility method to find LIS using Dynamic programming static int computeLIS(int circBuff[], int start, int end, int n) { int LIS[] = new int[n+end-start]; /* Initialize LIS values for all indexes */ for (int i = start; i < end; i++) LIS[i] = 1; /* Compute optimized LIS values in bottom up manner */ for (int i = start + 1; i < end; i++) // Set j on the basis of current window // i.e. first element of the current window for (int j = start; j < i; j++ ) if (circBuff[i] > circBuff[j] && LIS[i] < LIS[j] + 1) LIS[i] = LIS[j] + 1; /* Pick maximum of all LIS values */ int res = Integer.MIN_VALUE; for (int i = start; i < end; i++) res = Math.max(res, LIS[i]); return res; } // Function to find Longest Increasing subsequence in // Circular manner static int LICS(int arr[], int n) { // Make a copy of given array by appending same // array elements to itself int circBuff[] = new int[2 * n]; for (int i = 0; i<n; i++) circBuff[i] = arr[i]; for (int i = n; i < 2*n; i++) circBuff[i] = arr[i-n]; // Perform LIS for each window of size n int res = Integer.MIN_VALUE; for (int i=0; i<n; i++) res = Math.max(computeLIS(circBuff, i, i + n, n), res); return res; } // Driver method public static void main(String args[]) { int arr[] = { 1, 4, 6, 2, 3 }; System.out.println("Length of LICS is " + LICS( arr, arr.length)); }} |
Python3
# Python3 implementation to find # LIS in circular way Utility # function to find LIS using # Dynamic programmidef computeLIS(circBuff, start, end, n): LIS = [0 for i in range(end)] # Initialize LIS values # for all indexes for i in range(start, end): LIS[i] = 1 # Compute optimized LIS values # in bottom up manner for i in range(start + 1, end): # Set j on the basis of current # window i.e. first element of # the current window for j in range(start,i): if (circBuff[i] > circBuff[j] and LIS[i] < LIS[j] + 1): LIS[i] = LIS[j] + 1 # Pick maximum of all LIS values res = -100000 for i in range(start, end): res = max(res, LIS[i]) return res# Function to find Longest Increasing # subsequence in Circular mannerdef LICS(arr, n): # Make a copy of given # array by appending same # array elements to itself circBuff = [0 for i in range(2 * n)] for i in range(n): circBuff[i] = arr[i] for i in range(n, 2 * n): circBuff[i] = arr[i - n] # Perform LIS for each # window of size n res = -100000 for i in range(n): res = max(computeLIS(circBuff, i, i + n, n), res) return res# Driver codearr = [ 1, 4, 6, 2, 3 ]n = len(arr)print("Length of LICS is", LICS(arr, n))# This code is contributed # by sahilshelangia |
C#
// C# implementation to find // LIS in circular wayusing System;class Test{ // Utility method to find LIS // using Dynamic programming static int computeLIS(int []circBuff, int start, int end, int n) { int []LIS = new int[n+end-start]; /* Initialize LIS values for all indexes */ for (int i = start; i < end; i++) LIS[i] = 1; /* Compute optimized LIS values in bottom up manner */ for (int i = start + 1; i < end; i++) // Set j on the basis of current window // i.e. first element of the current window for (int j = start; j < i; j++ ) if (circBuff[i] > circBuff[j] && LIS[i] < LIS[j] + 1) LIS[i] = LIS[j] + 1; /* Pick maximum of all LIS values */ int res = int.MinValue; for (int i = start; i < end; i++) res = Math.Max(res, LIS[i]); return res; } // Function to find Longest Increasing // subsequence in Circular manner static int LICS(int []arr, int n) { // Make a copy of given array by // appending same array elements to itself int []circBuff = new int[2 * n]; for (int i = 0; i<n; i++) circBuff[i] = arr[i]; for (int i = n; i < 2*n; i++) circBuff[i] = arr[i-n]; // Perform LIS for each window of size n int res = int.MinValue; for (int i=0; i<n; i++) res = Math.Max(computeLIS(circBuff, i, i + n, n), res); return res; } // Driver method public static void Main() { int []arr = {1, 4, 6, 2, 3}; Console.Write("Length of LICS is " + LICS( arr, arr.Length)); }}// This code is contributed by nitin mittal. |
PHP
<?php// PHP implementation to// find LIS in circular way// Utility function to find // LIS using Dynamic programmingfunction computeLIS($circBuff, $start, $end, $n){ $LIS = Array(); /* Initialize LIS values for all indexes */ for ($i = $start; $i < $end; $i++) $LIS[$i] = 1; /* Compute optimized LIS values in bottom up manner */ for ($i = $start + 1; $i < $end; $i++) // Set j on the basis of // current window // i.e. first element of // the current window for ( $j = $start; $j < $i; $j++ ) if ($circBuff[$i] > $circBuff[$j] && $LIS[$i] < $LIS[$j] + 1) $LIS[$i] = $LIS[$j] + 1; /* Pick maximum of all LIS values */ $res = PHP_INT_MIN; for ($i = $start; $i < $end; $i++) $res = max($res, $LIS[$i]); return $res;}// Function to find LIS // in Circular mannerfunction LICS($arr, $n){ // Make a copy of given array // by appending same array // elements to itself for ($i = 0; $i < $n; $i++) $circBuff[$i] = $arr[$i]; for ($i = $n; $i < 2 * $n; $i++) $circBuff[$i] = $arr[$i - $n]; // Perform LIS for each // window of size n $res = PHP_INT_MIN; for ($i = 0; $i < $n; $i++) $res = max(computeLIS($circBuff, $i, $i + $n, $n), $res); return $res;}// Driver Code$arr = array(1, 4, 6, 2, 3);$n = sizeof($arr);echo "Length of LICS is " , LICS($arr, $n); // This code is contributed by aj_36?> |
Javascript
<script> // Javascript implementation to find LIS in circular way // Utility method to find LIS // using Dynamic programming function computeLIS(circBuff, start, end, n) { let LIS = new Array(n+end-start); /* Initialize LIS values for all indexes */ for (let i = start; i < end; i++) LIS[i] = 1; /* Compute optimized LIS values in bottom up manner */ for (let i = start + 1; i < end; i++) // Set j on the basis of current window // i.e. first element of the current window for (let j = start; j < i; j++ ) if (circBuff[i] > circBuff[j] && LIS[i] < LIS[j] + 1) LIS[i] = LIS[j] + 1; /* Pick maximum of all LIS values */ let res = Number.MIN_VALUE; for (let i = start; i < end; i++) res = Math.max(res, LIS[i]); return res; } // Function to find Longest Increasing // subsequence in Circular manner function LICS(arr, n) { // Make a copy of given array by // appending same array elements to itself let circBuff = new Array(2 * n); for (let i = 0; i<n; i++) circBuff[i] = arr[i]; for (let i = n; i < 2*n; i++) circBuff[i] = arr[i-n]; // Perform LIS for each window of size n let res = Number.MIN_VALUE; for (let i=0; i<n; i++) res = Math.max(computeLIS(circBuff, i, i + n, n), res); return res; } let arr = [1, 4, 6, 2, 3]; document.write("Length of LICS is " + LICS( arr, arr.length)); </script> |
Output :
Length of LICS is 4
Time Complexity: O(n3). It can be reduced O(n2 Log n) using O(n Log n) algorithm to find LIS.
Auxiliary Space: O(n)
Reference :
https://www.careercup.com/question?id=5942735794077696
This article is contributed by Sahil Chhabra. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
