这是通过动态编程解决的。让 M [i] 仅是 x i 个元素的***解决方案/ code>。然后：

This is solved by dynamic programming. Let M[i] be the best solution only for the first i elements of x. Then:

M[i] = 0 for i < L
M[i] = max(M[i-1], M[i-L] + sum(x[i-L+1] + x[i-L+2] + ... + x[i]))

您的问题的解决方案是 M [N] 。

The solution to your problem is M[N].

编写代码时，您可以递增地计算总和（或简单地预先计算所有总和），得出O（ N ）解决方案。

When you code it, you can incrementally compute the sum (or simply pre-compute all the sums) leading to an O(N) solution in both space and time.

如果您必须精确地找到 K 子集，可以通过定义 M [i，k] 来扩展此范围，以使其成为 k $ c的最优解前 i 个元素上的$ c>个子集。然后：

If you have to find exactly K subsets, you can extend this, by defining M[i, k] to be the optimal solution with k subsets on the first i elements. Then:

M[i, k] = 0 for i < k * L or k = 0.
M[i, k] = max(M[i-1, k], M[i-L, k-1] + sum(x[i-L+1] + ... + x[i])

解决问题的方法是 M [N，K] 。

这是二维动态编程解决方案，其时空复杂度为O（ NK ）（假设您使用与上述相同的技巧来避免重新计算总和）。

This is a 2d dynamic programming solution, and has time and space complexity of O(NK) (assuming you use the same trick as above for avoiding re-computing the sum).