用 Python 编写程序来查找循环子列表的最大和

pythonserver side programmingprogramming更新于 2026/1/17 23:40:17

假设我们有一个数字列表 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 中的每个数字，执行
- 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))