Python 中查找列表中非邻接元素最大和的程序

假设我们有一个名为 nums 的数字列表，我们将定义一个返回非邻接数字最大和的函数。这里的数字可以是 0 或负数。

因此，如果输入像 [3, 5, 7, 3, 6]，则输出将是 16，因为我们可以取 3、7 和 6 来获得 16。

为了解决这个问题，我们将遵循以下步骤−

  • 如果 nums 的大小 <= 2，则

    • 返回 nums 的最大值

  • noTake := 0

  • take := nums[0]

  • 对于 nums 从 1 到 nums 的大小的范围，执行

    • take := noTake + nums[i]

    • noTake := noTake 和 take 的最大值

  • 返回 noTake 和 take 的最大值

让我们看看下面的实现来更好地理解 −

示例

 在线演示

class Solution:
   def solve(self, nums):
      if len(nums) <= 2:
         return max(nums)
      noTake = 0
      take = nums[0]
      for i in range(1, len(nums)):
         take, noTake = noTake + nums[i], max(noTake, take)
         return max(noTake, take)
ob = Solution()
nums = [3, 5, 7, 3, 6]
print(ob.solve(nums))

输入

[3, 5, 7, 3, 6]

输出

16

更新时间:2020 年 10 月 9 日

730 次浏览

开启你的职业生涯

完成课程获得认证

立即开始
广告