Circular Longest Increasing Subsequence

1
votes

How can I find the length of Longest Increasing Sub-sequence if the numbers are arranged in circular fashion. For example:

LIS of 3, 2, 1 is 3 [1, 2, 3].

P.S I know how to solve Linear LIS in O(nlogn).

Problem Source: https://www.codechef.com/problems/D2/

Update: The LIS has to be calculated by going through the circle only once. Example 2: LIS of 1, 4, 3 is 2 and that could be either of 1, 3 or 1, 4 or 3, 4.
Thanks

1
algorithmlis
Is this a homework assignment? – Tim Biegeleisen
@TimBiegeleisen Of course not..!! What made you think so? I was learning DP from this source codechef.com/wiki/tutorial-dynamic-programming and this problem was mentioned as a practice problem in the tutorial. – bewithaman
@user3518014 what would be the output of this input: 4, 1, 2, 2, 3. will it be 4 or 5 ? – surajs1n
4 formed by: 1, 2, 3, 4 – bewithaman
You could apply LIS to every rotation of the array. Would be O(n^2 log n). – IVlad

1 Answers

0
votes

The example in question is wrong. circular rotation of [1,2,3] would be [2,3,1] or [3,1,2].

In which case, we can solve it similar way as longest increasing subsequence. As:

  1. Sort the list in ascending order.

  2. Find min element in the original list.

  3. Start iteration from min_index in original list and compare it with sorted list, and create intermediate array L[i][j] with same logic as longest common subsequence. i will vary from min_index to (i+n-1)%n
  4. Finally return L[max_index][n]