Chương trình tìm tổng các phần tử không liền kề trong danh sách hình tròn trong python

Giả sử chúng ta có một danh sách các số được gọi là nums đại diện cho một danh sách hình tròn. Chúng ta phải tìm tổng lớn nhất của các số không liền kề.

Vì vậy, nếu đầu vào là nums =[10, 3, 4, 8], thì đầu ra sẽ là 14, vì chúng ta có thể lấy 10 và 4. Chúng ta không thể lấy 10 và 8 vì chúng liền nhau.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums
• nums1:=nums [từ chỉ mục 0 đến n - 2]
• nums2:=nums [từ chỉ mục 1 đến cuối]
• Định nghĩa một hàm f (). Điều này sẽ khiến tôi mất
• if i> =size of nums1, then
  • trả về 0
• trả về tối đa nums1 [i] + f (i + 2) và f (i + 1)
• Định nghĩa một hàm g (). Điều này sẽ mất j
• nếu j> =kích thước của nums2, thì
  • trả về 0
• trả về tối đa là nums2 [j] + g (j + 2) và g (j + 1)
• Từ phương thức chính, hãy làm như sau -
• trả về giá trị tối đa là f (0) và g (0)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

[10, 3, 4, 8]

Đầu ra

14