Last Updated: 12 Sep, 2021

Longest Increasing Subsequence in Circular Manner

Moderate

Asked in company

Solve now

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.

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

Solve now

Approaches

01 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”.

Solve now

02 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 “lisUsingDP” 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 “lisUsingDP” function:
- Take an array “dp” of size ‘n’ and initialize it with 1.
- Iterate through the loop from 1 to n - 1(say iterator be i):
  - Iterate through the loop from 0 to i(say iterator be j):
    - If “newArr[i]” > “newArr[j]” and dp[i] <= dp[j]:
      - Update “dp[i]” = “dp[j]” + 1.
- Iterate through the dp array from 0 to n-1(say iterator be i):
  - If “lis” is less than dp[i], update “lis” = “dp[i]”.
- Return “lis”.

Solve now

03 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 “lisUsingBS” 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 “lisUsingBS” function:
- Take an array “minElement” of size ‘n’.
- Take an integer “len” to store the longest increasing subsequence.
- Update “minElement[0]” = “newArr[0]”.
- Iterate through the loop from 1 to n - 1(say iterator be i):
  - If “newArr[i]” is greater than “minElement[len]” then increment “len” by 1 and update “minElement[len] = “newArr[i]”.
  - Else Binary Search the “index” of lower bound of “newArr[i]” and update the value of “minElement[index]” = “newArr[i]”.
- Return “len + 1”.

Solve now