Given an array containing n numbers. The problem is to find the length of the longest contiguous subarray in a circular manner such that every element in the subarray is strictly greater than its previous element in the same subarray. Time Complexity should be O(n).
Examples:
Input : arr[] = {2, 3, 4, 5, 1}
Output : 5
{2, 3, 4, 5, 1} is the subarray if we circularly
start from the last element and then take the
first four elements. This will give us an increasing
subarray {1, 2, 3, 4, 5} in a circular manner.
Input : arr[] = {2, 3, 8, 4, 6, 7, 10, 12, 9, 1}
Output : 5
Method 1 (Using extra space): Make a temp[] array of size 2*n. Copy the elements of arr[] in temp[] two times. Now, find length of Longest increasing subarray in temp[].
Method 2 (Without using extra space):
Following are the steps:
- If n == 1, return 1.
- Find length of longest increasing subarray starting with first element of arr[]. Let its length be startLen.
- Starting from the next element where the first increasing subarray ends, find the length of the longest increasing subarray. Let it be max.
- Consider the length of the increasing subarray that ends with the last element of arr[]. Let it be endLen.
- If arr[n-1] < arr[0], then endLen = endLen + startLen.
- Finally, return maximum of (max, endLen, startLen).
Implementation:
C++
// C++ implementation to find length of longest// increasing circular subarray#include <bits/stdc++.h>using namespace std;// function to find length of longest// increasing circular subarrayint longlenCircularSubarr(int arr[], int n){ // if there is only one element if (n == 1) return 1; // 'startLen' stores the length of the longest // increasing subarray which starts from // first element int startLen = 1, i; int len = 1, max = 0; // finding the length of the longest // increasing subarray starting from // first element for (i = 1; i < n; i++) { if (arr[i - 1] < arr[i]) startLen++; else break; } if (max < startLen) max = startLen; // traverse the array index (i+1) for (int j = i + 1; j < n; j++) { // if current element if greater than previous // element, then this element helps in building // up the previous increasing subarray encountered // so far if (arr[j - 1] < arr[j]) len++; else { // check if 'max' length is less than the length // of the current increasing subarray. If true, // then update 'max' if (max < len) max = len; // reset 'len' to 1 as from this element // again the length of the new increasing // subarray is being calculated len = 1; } } // if true, then add length of the increasing // subarray ending at last element with the // length of the increasing subarray starting // from first element - This is done for // circular rotation if (arr[n - 1] < arr[0]) len += startLen; // check if 'max' length is less than the length // of the current increasing subarray. If true, // then update 'max' if (max < len) max = len; return max;}// Driver program to test aboveint main(){ int arr[] = { 2, 3, 4, 5, 1 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Length = " << longlenCircularSubarr(arr, n); return 0;} |
Java
// Java implementation to find length// of longest increasing circular subarrayclass Circular{ // function to find length of longest // increasing circular subarray public static int longlenCircularSubarr(int arr[], int n) { // if there is only one element if (n == 1) return 1; // 'startLen' stores the length of the // longest increasing subarray which // starts from first element int startLen = 1, i; int len = 1, max = 0; // finding the length of the longest // increasing subarray starting from // first element for (i = 1; i < n; i++) { if (arr[i - 1] < arr[i]) startLen++; else break; } if (max < startLen) max = startLen; // traverse the array index (i+1) for (int j = i + 1; j < n; j++) { // if current element if greater than // previous element, then this element // helps in building up the previous // increasing subarray encountered so far if (arr[j - 1] < arr[j]) len++; else { // check if 'max' length is less than // the length of the current increasing // subarray. If true, then update 'max' if (max < len) max = len; // reset 'len' to 1 as from this element // again the length of the new increasing // subarray is being calculated len = 1; } } // if true, then add length of the increasing // subarray ending at last element with the // length of the increasing subarray starting // from first element - This is done for // circular rotation if (arr[n - 1] < arr[0]) len += startLen; // check if 'max' length is less than the // length of the current increasing subarray. // If true, then update 'max' if (max < len) max = len; return max; } // driver code public static void main(String[] args) { int arr[] = { 2, 3, 4, 5, 1 }; int n = 5; System.out.print("Length = "+ longlenCircularSubarr(arr, n)); }}// This code is contributed by rishabh_jain |
Python3
# Python3 implementation to find length# of longest increasing circular subarray# function to find length of longest# increasing circular subarraydef longlenCircularSubarr (arr, n): # if there is only one element if n == 1: return 1 # 'startLen' stores the length of the # longest increasing subarray which # starts from first element startLen = 1 len = 1 max = 0 # finding the length of the longest # increasing subarray starting from # first element for i in range(1, n): if arr[i - 1] < arr[i]: startLen+=1 else: break if max < startLen: max = startLen # traverse the array index (i+1) for j in range(i + 1, n): # if current element if greater than # previous element, then this element # helps in building up the previous # increasing subarray encountered # so far if arr[j - 1] < arr[j]: len+=1 else: # check if 'max' length is less # than the length of the current # increasing subarray. If true, # then update 'max' if max < len: max = len # reset 'len' to 1 as from this # element again the length of the # new increasing subarray is # being calculated len = 1 # if true, then add length of the increasing # subarray ending at last element with the # length of the increasing subarray starting # from first element - This is done for # circular rotation if arr[n - 1] < arr[0]: len += startLen # check if 'max' length is less than the # length of the current increasing subarray. # If true, then update 'max' if max < len: max = len return max# Driver code to test abovearr = [ 2, 3, 4, 5, 1 ]n = len(arr)print("Length = ",longlenCircularSubarr(arr, n))# This code is contributed by "Sharad_Bhardwaj". |
C#
// C# implementation to find length// of longest increasing circular subarrayusing System;public class GFG { // function to find length of longest // increasing circular subarray static int longlenCircularSubarr(int[] arr, int n) { // if there is only one element if (n == 1) return 1; // 'startLen' stores the length of the longest // increasing subarray which starts from // first element int startLen = 1, i; int len = 1, max = 0; // finding the length of the longest // increasing subarray starting from // first element for (i = 1; i < n; i++) { if (arr[i - 1] < arr[i]) startLen++; else break; } if (max < startLen) max = startLen; // traverse the array index (i+1) for (int j = i + 1; j < n; j++) { // if current element if greater than previous // element, then this element helps in building // up the previous increasing subarray encountered // so far if (arr[j - 1] < arr[j]) len++; else { // check if 'max' length is less than the length // of the current increasing subarray. If true, // then update 'max' if (max < len) max = len; // reset 'len' to 1 as from this element // again the length of the new increasing // subarray is being calculated len = 1; } } // if true, then add length of the increasing // subarray ending at last element with the // length of the increasing subarray starting // from first element - This is done for // circular rotation if (arr[n - 1] < arr[0]) len += startLen; // check if 'max' length is less than the length // of the current increasing subarray. If true, // then update 'max' if (max < len) max = len; return max; } // Driver program to test above static public void Main() { int[] arr = { 2, 3, 4, 5, 1 }; int n = arr.Length; Console.WriteLine("Length = " + longlenCircularSubarr(arr, n)); // Code }}// This code is contributed by vt_m. |
PHP
<?php // PHP implementation to find length of longest// increasing circular subarray// function to find length of longest// increasing circular subarrayfunction longlenCircularSubarr(&$arr, $n){ // if there is only one element if ($n == 1) return 1; // 'startLen' stores the length of the longest // increasing subarray which starts from // first element $startLen = 1; $len = 1; $max = 0; // finding the length of the longest // increasing subarray starting from // first element for ($i = 1; $i < $n; $i++) { if ($arr[$i - 1] < $arr[$i]) $startLen++; else break; } if ($max < $startLen) $max = $startLen; // traverse the array index (i+1) for ($j = $i + 1; $j < $n; $j++) { // if current element if greater than // previous element, then this element // helps in building up the previous // increasing subarray encountered // so far if ($arr[$j - 1] < $arr[$j]) $len++; else { // check if 'max' length is less than // the length of the current increasing // subarray. If true, then update 'max' if ($max < $len) $max = $len; // reset 'len' to 1 as from this element // again the length of the new increasing // subarray is being calculated $len = 1; } } // if true, then add length of the increasing // subarray ending at last element with the // length of the increasing subarray starting // from first element - This is done for // circular rotation if ($arr[$n - 1] < $arr[0]) $len += $startLen; // check if 'max' length is less than the length // of the current increasing subarray. If true, // then update 'max' if ($max < $len) $max = $len; return $max;}// Driver Code$arr = array( 2, 3, 4, 5, 1 );$n = sizeof($arr);echo "Length = " . longlenCircularSubarr($arr, $n);// This code is contributed by ita_c?> |
Javascript
<script>// Javascript implementation to find length// of longest increasing circular subarray // function to find length of longest // increasing circular subarray function longlenCircularSubarr(arr,n) { // if there is only one element if (n == 1) return 1; // 'startLen' stores the length of the // longest increasing subarray which // starts from first element let startLen = 1, i; let len = 1, max = 0; // finding the length of the longest // increasing subarray starting from // first element for (i = 1; i < n; i++) { if (arr[i - 1] < arr[i]) startLen++; else break; } if (max < startLen) max = startLen; // traverse the array index (i+1) for (let j = i + 1; j < n; j++) { // if current element if greater than // previous element, then this element // helps in building up the previous // increasing subarray encountered so far if (arr[j - 1] < arr[j]) len++; else { // check if 'max' length is less than // the length of the current increasing // subarray. If true, then update 'max' if (max < len) max = len; // reset 'len' to 1 as from this element // again the length of the new increasing // subarray is being calculated len = 1; } } // if true, then add length of the increasing // subarray ending at last element with the // length of the increasing subarray starting // from first element - This is done for // circular rotation if (arr[n - 1] < arr[0]) len += startLen; // check if 'max' length is less than the // length of the current increasing subarray. // If true, then update 'max' if (max < len) max = len; return max; } // driver code let arr=[2, 3, 4, 5, 1 ]; let n = 5; document.write("Length = "+ longlenCircularSubarr(arr, n)); // This code is contributed by avanitrachhadiya2155</script> |
Output
Length = 5
Time Complexity: O(n).
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!
