在Python中找到两个非重叠子列表的最大和的程序

在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)插入到列表的末尾
  • 定义一个名为solve()的函数。这将采用len1,len2
  • Q:列表,其中len1的元素为(P[i + len1] – P[i]),其中i在0到P大小-len1的范围内
  • prefix:Q的副本
  • 对于前缀中的第i个元素,在0到前缀大小-1的范围内,执行以下操作
    • prefix[i + 1]:前缀[i + 1]和前缀[i]的最大值
  • ans:-无限大
  • 对于P的长度为len1到len2的范围内的i,执行以下操作
    • left:前缀[i – len1]
    • right:P[i + len2] – P[i]
    • ans:ans和(left + right)的最大值
  • 返回ans
  • 从main方法执行以下操作−
  • 返回解析(len1,len2),解析(len2,len1)的最大值

以下是实现示例以便更好地理解−

更多Python相关文章,请阅读:Python 教程

例子

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程