python - 有限制的长度为 L 的子序列的最大和
问题描述
给定一个正整数数组。如何找到一个长度L
为max
总和的子序列,其任意两个相邻元素之间的距离不超过K
我有以下解决方案,但不知道如何考虑长度 L。
1 <= N <= 100000, 1 <= L <= 200, 1 <= K <= N
f[i] 包含以 i 结尾的子序列的最大总和。
for i in range(K, N)
f[i] = INT_MIN
for j in range(1, K+1)
f[i] = max(f[i], f[i-j] + a[i])
return max(f)
解决方案
(编辑:稍微简化的非递归解决方案)
您可以这样做,只是为每次迭代考虑是否应包含或排除该项目。
def f(maxK,K, N, L, S):
if L == 0 or not N or K == 0:
return S
#either element is included
included = f(maxK,maxK, N[1:], L-1, S + N[0] )
#or excluded
excluded = f(maxK,K-1, N[1:], L, S )
return max(included, excluded)
assert f(2,2,[10,1,1,1,1,10],3,0) == 12
assert f(3,3,[8, 3, 7, 6, 2, 1, 9, 2, 5, 4],4,0) == 30
如果 N 很长,您可以考虑更改为表格版本,也可以将输入更改为元组并使用记忆化。
由于 OP 后来包含了 N 可以是 100 000 的信息,所以我们不能真正使用这样的递归解决方案。所以这是一个在 O(n K L) 中运行的解决方案,具有相同的内存要求:
import numpy as np
def f(n,K,L):
t = np.zeros((len(n),L+1))
for l in range(1,L+1):
for i in range(len(n)):
t[i,l] = n[i] + max( (t[i-k,l-1] for k in range(1,K+1) if i-k >= 0), default = 0 )
return np.max(t)
assert f([10,1,1,1,1,10],2,3) == 12
assert f([8, 3, 7, 6, 2, 1, 9],3,4) == 30
非递归解决方案的解释。表 t[ i, l ] 中的每个单元格表示最大子序列的值,其中恰好有 l 个元素使用位置 i 中的元素,并且只有位置 i 或更低位置的元素,其中元素之间的距离最多为 K。
长度为 n 的子序列(t[i,1] 中的子序列必须只有一个元素 n[i] )
较长的子序列有 n[i] + 一个由 l-1 个元素组成的子序列,最多从前 k 行开始,我们选择具有最大值的那个。通过这种方式迭代,我们确保这个值已经被计算出来。
考虑到您只查看最多 K 步,可以进一步改进内存。
推荐阅读
- elasticsearch - 使用 streaming_bulk() 时出现 409 错误 - 确定该文档仅包含一次。
- mongodb - MongoDB Java 驱动程序聚合字符串
- android - MPCharts 条形图 X 标签且无法滚动
- javascript - 如何打印酶的浅包装内容
- gcc - 检测 Linux 内核函数
- javascript - 将日期时间字符串从 C# 转换为 Javascript 中的日期对象
- php - 如何获取查询中的所有值?
- javascript - 如何在 ASP.NET 中引用 ItemTemplate 中的文本框
- office365 - EWS 模拟可以与 Office365 电子邮件帐户服务提供商一起使用吗?
- ubuntu - sed 命令不更改文本