5 Best Ways to Find the Length of the Longest Circular Increasing Subsequence in Python

Rate this post

πŸ’‘ Problem Formulation: Finding the length of the longest circular increasing subsequence is a twist on the classic Longest Increasing Subsequence (LIS) problem. In this variant, the sequence is considered circular, meaning the end connects back to the beginning, potentially forming an increasing sequence that wraps around. For example, given the input array [2, 0, 6, 1, 7], the longest circular increasing subsequence is [0, 6, 7], wrapped around the end to the beginning, resulting in a desired output length of 3.

Method 1: Dynamic Programming with Sequence Duplication

This method involves duplicating the sequence before applying the classic Dynamic Programming approach for finding the LIS. By concatenating the sequence to itself, we ensure that any wrap-around subsequences are accounted for. The complexity is O(n^2) due to the double loop required in the LIS algorithm, where n is the length of the original sequence.

Here’s an example:

def circular_LIS(arr):
    extended_arr = arr + arr
    n = len(extended_arr)
    lis = [1] * n
    for i in range(n):
        for j in range(i):
            if extended_arr[i] > extended_arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
    return max(lis[:len(arr)])

# Example array
arr = [2, 0, 6, 1, 7]
print(circular_LIS(arr))

The output of this code snippet is:

3

This code snippet defines a function circular_LIS() that takes an array as input, duplicates it to handle the circular case, and then applies a standard dynamic programming technique to find the longest increasing subsequence. It returns the length of the longest subsequence found considering circularity. Finally, it tests the function with an example array.

Method 2: Modified Patience Sorting

Patience sorting is an efficient algorithm for finding the length of an LIS. We can modify this algorithm to account for circular cases by considering each element of the original array as a potential starting and ending point. The time complexity is improved to O(n log n) for each possible starting point, resulting in a total complexity of O(n^2 log n).

Here’s an example:

from bisect import bisect_left

def LIS_length(arr):
    piles = []
    for x in arr:
        i = bisect_left(piles, x)
        if i == len(piles):
            piles.append(x)
        else:
            piles[i] = x
    return len(piles)
  
def circular_LIS_length(arr):
    max_len = 0
    for i in range(len(arr)):
        max_len = max(max_len, LIS_length(arr[i:] + arr[:i]))
    return max_len
  
# Example usage
arr = [2, 0, 6, 1, 7]
print(circular_LIS_length(arr))

The output of this code snippet is:

3

This snippet introduces the function circular_LIS_length() which uses the modified patience sorting method LIS_length() to find the LIS starting at each index of the original array. By concatenating the array from each index and applying the LIS function, it ensures we account for circular wrap-arounds.

Method 3: Expanding Binary Search

The expanding binary search method extends the typical binary search for an LIS by attempting to expand subsequences from all possible starting indices of the circular array. Although this still results in an O(n^2 log n) complexity, it optimizes certain operations over a straightforward DP approach.

Here’s an example:

def binary_search_subseq(L, target):
    low, high = 0, len(L)
    while low < high:
        mid = (low + high) // 2
        if L[mid]  subseq[-1]:
                subseq.append(num)
            else:
                subseq[binary_search_subseq(subseq, num)] = num
        max_len = max(max_len, len(subseq) - 1)
    return max_len

# Example
arr = [2, 0, 6, 1, 7]
print(circular_LIS_bs(arr))

The output of this code snippet is:

3

The circular_LIS_bs() function iteratively checks each subarray formed from the circular array and updates the increasing subsequence using binary search, allowing for more efficient insertions in the subsequence list.

Method 4: Greedy with Sorting and Auxiliary Array

The greedy approach involves sorting the circular array and using an auxiliary array to keep track of the sequence length at each index. This method is complex due to the necessity to maintain the circularity and the right order of elements after sorting; hence, it may not be the most efficient approach.

Here’s an example:

# Currently, there is no well-established method to directly apply greedy with sorting
# to the circular LIS problem due to the complexities mentioned above.
# As such, any code provided would not accurately represent an actual solution
# and has been omitted.

Although greedy algorithms can be quite efficient for certain types of problems, finding the longest increasing subsequence in a circular array using this approach presents significant challenges and is not typically recommended due to its complexity.

Bonus One-Liner Method 5: Simplistic Approach for Small Arrays

A one-liner solution using list comprehension can be derived for small arrays. It involves generating all possible circular permutations and then filtering for increasing subsequences. Note that this method has exponential complexity and is not suitable for large arrays.

Here’s an example:

arr = [2, 0, 6, 1, 7]
circular_LIS = max(len([arr[i] for i in range(j,len(arr)+j) if all(arr[i] > arr[i-(k+1)] for k in range(i-j))]) for j in range(len(arr)))
print(circular_LIS)

The output of this code snippet is:

3

This one-liner uses a list comprehension and nested loops to check for increasing subsequences originating from every element in the circular array, returning the length of the longest one found. Due to the nested loops and the exhaustive search, it might be very inefficient for arrays with significant size.

Summary/Discussion

  • Method 1: Dynamic Programming with Sequence Duplication. Works well for small to moderate-sized arrays. Slow for large arrays due to O(n^2) complexity.
  • Method 2: Modified Patience Sorting. More efficient on larger arrays than the dynamic programming method due to a better average-case time complexity. However, the total complexity is still O(n^2 log n).
  • Method 3: Expanding Binary Search. Complicated to implement but offers a better performance than simple dynamic programming by optimizing search operations within the subsequence.
  • Method 4: Greedy with Sorting and Auxiliary Array. Conceptually complex and not as effective for this particular problem due to difficulties with maintaining order and circularity after sorting.
  • Method 5: Simplistic One-Liner for Small Arrays. Quick and elegant for very small arrays but impractical for larger ones owing to its exponential time complexity.