Python程序：查找环形子列表的最大和

假设我们有一个数字列表nums，现在考虑一个nums的环形列表，其中nums的开头和结尾是相邻的。我们必须找到环形列表中非空子列表的最大和。

因此，如果输入类似于nums = [2, 3, -7, 4, 5]，则输出将为14，因为我们可以取子列表[4, 5, 2, 3]，其和为14。

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

  • max_sum := 负无穷大，cur_max := 0

  • min_sum := 正无穷大，cur_min := 0

  • 对于nums中的每个num，执行：

    • cur_max := num和cur_max + num中的最大值

    • max_sum := max_sum和cur_max中的最大值

    • cur_min := num和cur_min + num中的最小值

    • min_sum := min_sum和cur_min中的最小值

  • 如果max_sum <= 0，则

    • 返回max_sum

  • 返回max_sum和(nums中所有元素的和 - min_sum)中的最大值

让我们看下面的实现以更好地理解：

示例

import math
class Solution:
   def solve(self, nums):
      max_sum = -math.inf
      cur_max = 0
      min_sum = math.inf
      cur_min = 0
      for num in nums:
         cur_max = max(num, cur_max + num)
         max_sum = max(max_sum, cur_max)
         cur_min = min(num, cur_min + num)
         min_sum = min(min_sum, cur_min)
      if max_sum <= 0:
         return max_sum
      return max(max_sum, sum(nums) - min_sum)
ob = Solution()
nums = [2, 3, -7, 4, 5]
print(ob.solve(nums))

输入

[2, 3, -7, 4, 5]

输出

14

更新于：2020年10月9日

浏览量：195

开启您的职业生涯

完成课程获得认证

开始学习
广告