BinarySearch 0693 Largest Sum of Non-Adjacent Numbers in Circular List

Problem statement

https://binarysearch.com/problems/Largest-Sum-of-Non-Adjacent-Numbers-in-Circular-List/

Solution

Equal to Leetcode 0213. House Robber II.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums):
        def rob_helper(nums):
            dp1, dp2 = 0, 0
            for num in nums:
                dp1, dp2 = dp2, max(dp1 + num, dp2)          
            return dp2

        if not nums: return 0
        return max(nums[0] + rob_helper(nums[2:-1]), rob_helper(nums[1:]))