在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