BinarySearch 0488 Circular Longest Increasing Subsequence

Problem statement

https://binarysearch.com/problems/Circular-Longest-Increasing-Subsequence/

Solution

For each of n possible shifts find LIS.

Complexity

It is O(n^2 log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        def LIS(nums):
            dp = [10**10] * (len(nums) + 1)
            for elem in nums: dp[bisect_left(dp, elem)] = elem  
            return dp.index(10**10)
        return max(LIS(nums[i:] + nums[:i]) for i in range(len(nums)))