파이썬의 순환 목록에서 인접하지 않은 요소의 합을 찾는 프로그램

<시간/>

순환 목록을 나타내는 nums라는 숫자 목록이 있다고 가정합니다. 인접하지 않은 숫자의 가장 큰 합을 찾아야 합니다.

따라서 입력이 nums =[10, 3, 4, 8]과 같으면 10과 4를 사용할 수 있으므로 출력은 14가 됩니다. 10과 8은 인접해 있으므로 사용할 수 없습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=숫자 크기
nums1 :=nums[인덱스 0부터 n - 2까지]
nums2 :=nums[인덱스 1부터 끝까지]
f() 함수를 정의합니다. 이것은 내가 걸릴 것입니다
i>=nums1의 크기이면
- 0을 반환
nums1[i] + f(i + 2) 및 f(i + 1)의 최대값을 반환
함수 g()를 정의합니다. 시간이 걸립니다.
j>=nums2의 크기이면
- 0을 반환
nums2[j] + g(j + 2) 및 g(j + 1)의 최대값을 반환
메인 방법에서 다음을 수행하십시오 -
f(0) 및 g(0)의 최대값을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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))

입력

[10, 3, 4, 8]