在Python中查找具有相同和的三个非重叠子列表的最大总和的程序

假设我们有一个名为nums的数字列表和另一个值k，我们必须查找给定大小为k的三个非重叠子列表的最大总和。

因此，如果输入为nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3] k = 3，则输出将为27，因为我们可以选择子列表[2, 2, 2]，[4, 4, 4]和[3, 3, 3]，总和为27。

要解决此问题，我们将按照以下步骤进行操作 −

P := [0]
对于A中的每个x，请执行以下操作
- 在P末尾插入P[-1] + x
Q := [P[i + K] – P[i] for i in range 0 to size of P – K]
prefix := Q[from index 0 to end]
suffix := Q[from index 0 to end]
对于范围在0到Q大小 – 1的每个i，请执行以下操作
- prefix[i + 1]的最大值 := prefix[i + 1]和prefix[i]中的最大值
- suffix[~(i + 1)]的最大值:= suffix[~(i + 1)]和suffix[~i]中的最大值
对于K到Q大小 – K – 1的每个索引i，ret = (Q[i] + prefix[i – K] + suffix[i + K])
返回ret的最大值

示例（Python）

让我们看一下以下实现以获得更好的理解 –

class Solution:
   def solve(self, A, K):
      P = [0]
      for x in A:
         P.append(P[-1] + x)
      Q = [P[i + K] - P[i] for i in range(len(P) - K)]
      prefix = Q[:]
      suffix = Q[:]
      for i in range(len(Q) - 1):
         prefix[i + 1] = max(prefix[i + 1], prefix[i])
         suffix[~(i + 1)] = max(suffix[~(i + 1)], suffix[~i])
      return max(Q[i] + prefix[i - K] + suffix[i + K] for i in range(K, len(Q) - K))
ob = Solution()
nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3]
k = 3
print(ob.solve(nums, k))