问题来自本地黑客马拉松: 我有一个按降序排列的正整数排序数组。例如 (9,4,2,1)。您可以遍历数组的 n 个元素以最大化总和(最初 n = 数组的大小)。当您从头到尾遍历数组时，您可以随时停止并重新从头开始，但这样做的代价是您会损失 1 个元素。例如，在这种情况下，最好的方法是 9,0,9,4。请注意，我已经停止，丢失了一个元素(因此是 0)并再次继续。
我想用动态规划来解决这个问题。我知道如何在 O(n^2) 中使用 DP 来做到这一点。我正在寻找一种以更好的时间复杂度执行此操作的算法。
最佳答案
您不想在重启之间的某个时间间隔内取 k 个数字，而在其他重启之间的时间间隔内取 k + 2 个数字；每次取 k + 1 总是至少一样好。这意味着，在给定重启次数的情况下，可以立即清楚模式应该是什么(尽可能均匀)。
在时间 O(n) 中，可以预先计算数组每个前缀的总和。然后，在时间 O(n) 中，遍历所有可能的重启计数，通过检查两个相邻前缀的总和并乘以每个的适当次数，在时间 O(1) 中计算每个总数。
关于arrays - 大小 n 的最大总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33709251/