序列中 n 个区间的最大总和

Question

我正在做一些编程 "kata"，这是编程（和武术）的技能培养练习。我想学习如何在更短的时间内解决这些算法，所以我需要发展我对模式的了解。最终我想解决越来越高效的时间复杂度（O(n)、O(n^2) 等），但现在我可以以任何效率开始找出解决方案。

问题：

给定 arr[10] = [4, 5, 0, 2, 5, 6, 4, 0, 3, 5]

给定各种片段长度，例如一个 3 长度的片段和两个 2 长度的片段，找到片段的最佳位置（或包含的最大总和）而不重叠片段。

比如这个数组和这些段的解是2，因为：

{4 5} 0 2 {5 6 4} 0 {3 5}

我在 whosebug.com 上发帖之前尝试过的内容：

我已阅读：

Algorithm to find maximum coverage of non-overlapping sequences. (I.e., the Weighted Interval Scheduling Prob.)

algorithm to find longest non-overlapping sequences

并且我观看了麻省理工学院的开放式课件并阅读了有关使用动态规划解决复杂问题的一般步骤，并完成了动态规划教程以通过记忆查找斐波那契数列。我想我可以应用记忆来解决这个问题，但我还没有找到方法。

动态规划的主题是将问题分解成子问题，通过迭代找到最优解。

我想出的（以面向对象的方式）是

foreach (segment) {
    - find the greatest sum interval with length of this segment

这会产生不正确的结果，因为分段并不总是适合这种方法。例如：

给定 arr[7] = [0, 3, 5, 5, 5, 1, 0] 和两个 3 长度段，

第一段需要 5, 5, 5，第二段没有空间。理想情况下，我应该记住这个场景并再次尝试该算法，这次避免将 5、5、5 作为首选。 这条路对吗？

我怎样才能以 "dynamic programming" 的方式解决这个问题？

Answer 1

如果你放置第一段，你会得到两个更小的子数组：将剩下的两个段中的一个或两个放入这些子数组之一是一个与原始问题形式相同的子问题.

所以这建议递归：放置第一个段，然后尝试将剩余段分配给子数组的各种组合，并最大化这些组合。然后你记住：子问题都采用一个数组和一个段大小列表，就像原始问题一样。

我不确定这是最好的算法，但它是 "direct" 动态规划方法建议的算法。

编辑：更详细：

评估函数的参数应该有两部分：一个是一对数字，代表被分析的子数组（在这个例子中最初是[0,6]），第二个是多组表示要分配的段长度的数字（本例中为 {3,3}）。然后在伪代码中你做这样的事情：

valuation( array_ends, the_segments):
    if sum of the_segments > array_ends[1] - array_ends[0]:
        return -infinity

    segment_length = length of chosen segment from the_segments
    remaining_segments = the_segments with chosen segment removed

    best_option = 0
    for segment_placement = array_ends[0] to array_ends[1] - segment_length:
         value1 = value of placing the chosen segment at segment_placement
         new_array1 = [array_ends[0],segment_placement]
         new_array2 = [segment_placement + segment_length,array_ends[1]]
         for each partition of remaining segments into seg1 and seg2:
             sub_value1 = valuation( new_array1, seg1)
             sub_value2 = valuation( new_array2, seg2)
             if value1 + sub_value1 + sub_value2 > best_option:
                  best_option = value1 + sub_value1 + sub_value2
    return best_option

此代码（以一个错误和拼写错误为模）计算估值，但它使用相同的参数多次调用估值函数。所以记忆化的想法是缓存这些结果并避免重新遍历树的等效部分。所以我们可以通过包装估值函数来做到这一点：

memoized_valuation(args):
    if args in memo_dictionary:
         return memo_dictionary[args]
    else:
         result = valuation(args)
         memo_dictionary[args] = result
         return result

当然，你现在需要把递归调用改成调用memoized_valuation.

序列中 n 个区间的最大总和

Maximum sum of n intervals in a sequence

algorithm

dynamic-programming