Longest Increasing Subsequence in Circular Manner

Moderate
0/80
profile
Contributed by
0 upvote
Asked in company
Adobe

Problem statement

You are given an array “arr” of length ‘n’. You have to find the length of the longest increasing subsequence of this array in a circular manner, i.e., if you start from the ith position in the array, then your array will be ‘i’ to n - 1 then 0 to i - 1.

An array ‘a’ is a subsequence of an array ‘b’, if ‘a’ can be obtained from ‘b’ by deleting several (possibly, zero or all) elements from the array.

For Example : 
arr = {10, 7, 3}
In this example, the longest increasing subsequence can be {3, 10}, {7, 10} or {3, 7}. Hence the answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the total number of elements in the array.

The next line contains ‘n’ integers denoting the elements of the array.
Output Format : 
For each test case, print a single integer “ans” denoting the length of the longest increasing subsequence.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10    
1 <= N <= 300
0 <= arr[i] <= 1000

Time limit: 1 sec
Sample Input 1 :
2
4
11 9 5 3
3
5 7 3
Sample Output 1 :
2
3
Explanation For Sample Input 1 :
In the first test case, there are 3 LIS(Longest Increasing Subsequence) of length 2.
{3, 11}, {5, 11}, {9, 11}.
Hence, the answer is 2.

In the second test case, the longest increasing subsequence is 3, 5, 7.
Hence the answer is 3.
Sample Input 2 :
2
5 
13 57 23 27 43
4
1 2 3 4
Sample Output 2 :
4
4
Hint

Calculate longest increasing subsequence for every element of the array using recursion.

Approaches (3)
Naive approach

In this approach, we will find the LCS for every element of the array and return the maximum possible LCS from it.
 

The steps are as follows: 

  • In the “main” function:
    • Take an integer “answer” to store the final answer.
    • Iterate through the array from 0 to n-1(say iterator be i):
      • Take a vector “newArr” to store the elements of the array from ‘i’ to n-1, 0 to i-1.
      • Take an integer “lis” to store the longest increasing subsequence for the array “newArr”.
      • Call the function “recursion” passing the “newArr” vector, an integer “index” = ‘n’ and and “lis” as reference.
      • Update the value of “answer” = max(“answer”, “lis”);
    • Return “answer”.
  • In the “recursion” function:
    • If “index” = 1, return 1.
    • Take two integers “res” and “len”.
    • Iterate through the loop from 1 to “index”(say iterator be i):
      • Call the “recursion” function again and store the value in “res”.
      • If “newArr[i-1]” < newArr[index] and “res” + 1 > “len”, update “len” = res + 1.
    • Check if the value of “lis” is less than “len” update “lis” = max(“lis, “len”).
    • Return “len”.
Time Complexity

O( N * 2 ^ N ), where N is the size of the array “arr”.

 

As we are iterating through the array and for each element checking every possible case.

Hence the time complexity is O( N * 2 ^ N ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Longest Increasing Subsequence in Circular Manner
Full screen
Console