Python程序：查找两个不相交子列表的最大和

假设我们有一个名为nums的数字列表和两个值x和y，我们需要找到nums中两个不相交子列表的最大和，这两个子列表的长度分别为x和y。

例如，如果输入为nums = [3, 2, 10, -2, 7, 6]，x = 3，y = 1，则输出为22，因为我们选择的长度为3的子列表为[3, 2, 10]，另一个子列表为[7]。

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

  • P := 一个包含单个元素0的列表
  • 对于A中的每个x，执行：
    • 将(P的最后一个元素 + x)插入到P的末尾
  • 定义一个函数solve()。它将接收len1, len2作为参数
  • Q := 一个列表，其元素为(P[i + len1] - P[i])，其中i的范围是从0到P的大小 - len1
  • prefix := Q的一个副本
  • 对于从0到prefix大小 - 1的每个i，执行：
    • prefix[i + 1] := prefix[i + 1]和prefix[i]中的最大值
  • ans := -infinity
  • 对于从len1到P的大小 - len2的每个i，执行：
    • left := prefix[i - len1]
    • right := P[i + len2] - P[i]
    • ans := ans和(left + right)中的最大值
  • 返回ans
  • 在主方法中执行以下操作：
  • 返回solve(len1, len2)和solve(len2, len1)中的最大值

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

示例

 在线演示

class Solution:
   def solve(self, A, len1, len2):
      P = [0]
      for x in A:
         P.append(P[-1] + x)
      def solve(len1, len2):
         Q = [P[i + len1] - P[i] for i in range(len(P) - len1)]
         prefix = Q[:]
         for i in range(len(prefix) - 1):
            prefix[i + 1] = max(prefix[i + 1], prefix[i])
            ans = float("-inf")
            for i in range(len1, len(P) - len2):
               left = prefix[i - len1]
               right = P[i + len2] - P[i]
            ans = max(ans, left + right)
            return ans
         return max(solve(len1, len2), solve(len2, len1))
ob = Solution()
nums = [3, 2, 10, -2, 7, 6]
x = 3
y = 1
print(ob.solve(nums, x, y))

输入

[3, 2, 10, -2, 7, 6], 3, 1

输出

22

更新于：2020年11月20日

246 次查看

开启您的职业生涯

完成课程获得认证

开始学习
广告