Python程式：查詢環形列表中非相鄰元素的總和

假設我們有一個名為 nums 的數字列表，它表示一個環形列表。我們必須找到非相鄰數字的最大總和。

因此，如果輸入類似於 nums = [10, 3, 4, 8]，則輸出將為 14，因為我們可以選擇 10 和 4。我們不能選擇 10 和 8，因為它們是相鄰的。

為了解決這個問題，我們將遵循以下步驟 -

• n := nums 的大小
• nums1 := nums[從索引 0 到 n - 2]
• nums2 := nums[從索引 1 到結尾]
• 定義一個函式 f()。它將接收 i
• 如果 i >= nums1 的大小，則
  • 返回 0
• 返回 nums1[i] + f(i + 2) 和 f(i + 1) 的最大值
• 定義一個函式 g()。它將接收 j
• 如果 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]

輸出

14

Arnab Chakraborty

更新於: 2020-11-19

243 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習