Largest Sum of Non-Adjacent Numbers in Circular List - Amazon Top Interview Questions

                        Solution in C++ :

int solve(vector<int>& nums) {
    int ans = nums.empty() ? 0 : max(0, nums[0]), N = nums.size();
    vector<int> dp(N + 1);
    for (int i=1; i<N; i++) {
        dp[i+1] = max(dp[i-1] + nums[i],  dp[i]);
        ans = max(ans, dp[i+1]);
    }
    fill(dp.begin(),dp.end(), 0);
    for (int i=0; i<N-1; i++) {
        dp[i+1] = max(i>=1 ? dp[i-1] + nums[i] : nums[i],  dp[i]);
        ans = max(ans, dp[i+1]);
    }
    return ans;
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, nums):
        @cache
        def largest_sum(cur, end):
            if cur > end:
                return 0
            # you have 2 options
            # 1. include current element and skip the next one (continue from cur +2)
            # 2. skip current element and continue from the next one
            return max(largest_sum(cur + 1, end), nums[cur] + largest_sum(cur + 2, end))

        # special case when you have only  1 element.
        if len(nums) == 1:
            return max(nums[0], 0)

        # Find the largest of tow sum arrays
        # nums[:len(nums)-1]  and nums[1:]
        ans = max(largest_sum(0, len(nums) - 2), largest_sum(1, len(nums) - 1))

        # it appears you can get an sum of 0 if subset of 0 elements
        return max(ans, 0)