在python中找到环形列表中非相邻元素的和
假设我们有一个表示环形列表的数字列表,我们必须找到非相邻数字的最大和。
因此,如果输入像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)的最大值
让我们看下面的实现以更好地理解。
更多Python相关文章,请阅读:Python 教程
示例
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