数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学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, len(P) - K)]
- prefix := Q[0:]
- suffix := Q[0:]
- 对于i in range(0, len(Q) -1)：
- prefix[i + 1] := max(prefix[i + 1], prefix[i])
- suffix[-(i + 1)] := max(suffix[-(i + 1)], suffix[-i])
- ret = [Q[i] + prefix[i - K] + suffix[i + K] for i in range(K, len(Q) - K - 1)]
- 返回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))
输入
[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], 3
输出
27
更新于：2020年12月12日
浏览量：106
广告