Program to find sum of non-adjacent elements in a circular list in python

Suppose we have a list of numbers called nums that is representing a circular list. We have to find the largest sum of non-adjacent numbers.

So, if the input is like nums = [10, 3, 4, 8], then the output will be 14, as we can take 10 and 4. We cannot take 10 and 8 as they are adjacent.

To solve this, we will follow these steps −

• n := size of nums
• nums1 := nums[from index 0 to n - 2]
• nums2 := nums[from index 1 to end]
• Define a function f() . This will take i
• if i >= size of nums1 , then
  • return 0
• return maximum of nums1[i] + f(i + 2) and f(i + 1)
• Define a function g() . This will take j
• if j >= size of nums2 , then
  • return 0
• return maximum of nums2[j] + g(j + 2) and g(j + 1)
• From the main method do the following −
• return maximum of f(0) and g(0)

Let us see the following implementation to get better understanding −

Example

 Live Demo

class Solution:    def solve(self, nums):       n = len(nums)       nums1 = nums[: n - 1]       nums2 = nums[1:]       def f(i):          if i >= len(nums1):             return 0          return max(nums1[i] + f(i + 2), f(i + 1))       def g(j):          if j >= len(nums2):             return 0          return max(nums2[j] + g(j + 2), g(j + 1))       return max(f(0), g(0)) ob = Solution() nums = [10, 3, 4, 8] print(ob.solve(nums))

Input

[10, 3, 4, 8]

Output

14