1 回答
TA贡献1770条经验 获得超3个赞
可以解决在给定的问题为O(n)使用dynamic programming通过维持前缀求和阵列快速计算大小为k的子阵列的总和与保持跟踪阵列,其记录在所述阵列的每个步骤所采取的行动沿。这是相同的实现:https : //ideone.com/VxKzUn
该方法背后的思想是,对于数组中的每个元素,我们可以选择从这个元素开始创建我们的子数组,或者将其保留并移动到下一个元素,从而为我们提供最佳子结构递归关系其中可以表述为:
f(n) = max{ sum(arr[n], .. , arr[n + k]) + f(n + k + 1), f(n + 1) }
from collections import defaultdict
dp = defaultdict(lambda: -1)
prefixsum = []
trace = []
def getSubArraySum(i, j):
if i == 0:
return prefixsum[j]
return (prefixsum[j] - prefixsum[i - 1])
def rec(cur, arr, k):
if cur >= len(arr):
return 0
if dp[cur] != -1:
return dp[cur]
# Assuming that all the elements in the array is positive,
# else set s1 and s2 to -Infinity
s1 = -1; s2 = -1
# If we choose the subarray starting at `cur`
if cur + k - 1 < len(arr):
s1 = getSubArraySum(cur, cur + k - 1) + rec(cur + k + 1, arr, k)
# If we ignore the subarray starting at `cur`
s2 = rec(cur + 1, arr, k)
dp[cur] = max(s1, s2)
if s1 >= s2:
trace[cur] = (True, cur + k + 1)
return s1
trace[cur] = (False, cur + 1)
return s2
def getTrace(arr, trace, k):
itr = 0
subArrays = []
while itr < len(trace):
if trace[itr][0]:
subArrays.append(arr[itr : itr + k])
itr = trace[itr][1]
return subArrays
def solve(arr, k):
global dp, trace, prefixsum
dp = defaultdict(lambda: -1)
trace = [(False, 0)] * len(arr)
prefixsum = [0] * len(arr)
prefixsum[0] = arr[0]
for i in range(1, len(arr)):
prefixsum[i] += prefixsum[i - 1] + arr[i]
print("Array :", arr)
print("Max sum: ", rec(0, arr, k))
print("Subarrays: ", getTrace(arr, trace, k))
print("-- * --")
solve([1, 2, 3, 4], 3)
solve([1, 2, 3, 1, 7, 9] , 2)
上面代码的输出是,
Array : [1, 2, 3, 4]
Max sum: 9
Subarrays: [[2, 3, 4]]
-- * --
Array : [1, 2, 3, 1, 7, 9]
Max sum: 21
Subarrays: [[2, 3], [7, 9]]
-- * --
添加回答
举报