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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习