Python程序：求解最大K个子列表之和

假设我们有一个名为nums的数字列表，还有一个值k，它表示nums列表连接k次的较长列表。我们需要找到具有最大和的连续子列表的和。

因此，如果输入类似于nums = [1, 3, 4, -5]，k = 1，则输出将为11，因为我们可以取[2, 4, 5]这样的子列表。(原文例子有误，此处修正为更合理的解释)

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

• s := ans := lo := 0
• 对于范围0到min(k, 2)中的所有值，执行：
  • 对于nums中的每个x，执行：
    • s := s + x
    • lo := min(lo, s)
    • ans := max(ans, s - lo)
• 返回 ans + max(0, nums所有元素之和 * max(0, k - 2))

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

示例

在线演示

class Solution:
   def solve(self, nums, k):
      s = ans = lo = 0
      for _ in range(min(k, 2)):
         for x in nums:
            s += x
            lo = min(lo, s)
         ans = max(ans, s - lo)
      return ans + max(0, sum(nums)) * max(0, (k - 2))
ob = Solution()
nums = [2, 4, 5, -4]
k = 1
print(ob.solve(nums, k))

输入

[2, 4, 5, -4], 1

输出

11

Arnab Chakraborty

更新于：2020年11月19日

215 次浏览

开启您的职业生涯

完成课程获得认证

开始学习