algorithm - 最大连续负和或最小正子序列和问题

Question

我们都听说过 bentley 的美丽的珍珠问题 求解最大子序列和:

maxsofar = 0;
maxcur = 0;
for (i = 0; i < n; i++) {
  maxcur = max(A[i] + maxcur, 0);
  maxsofar = max(maxsofar, maxcur);
}

如果我们添加一个小于 M 的附加条件最大子序列会怎样？

Answer 1

这应该做到这一点。我说得对吗？

int maxsofar = 0;
for (int i = 0; i < n - 1; i++) {
   int maxcur = 0;
   for (int j = i; j < n; j++) {
      maxcur = max(A[j] + maxcur, 0);
      maxsofar = maxcur < M ? max(maxsofar, maxcur) : maxsofar;
   }
}

不幸的是，这是 O(n^2)。当 maxcur >=M 时，您可以通过打破内部循环来加快它的速度，但仍然 n^2 仍然存在。