找到 n 个连续数字的最大和，其中 sum < k

Question

我得到一个数组，要求我找出 n 个连续数字的最大可能总和，其中最大总和小于给定值 k。例如：

array = {1, 3, 1, 2, 3, 4, 1}
k = 7

这里，答案一定是6，因为我们可以得到的最大和是小于7的是：arr[1] + arr[2] + arr[3] = 3 + 1 + 2 = 6 我如何编写算法来找到这样的值？

（我已经用嵌套的for循环完成了，但是太花时间了，有没有其他方法可以让这个程序运行？）

Answer 1

基础

首先，我建议您阅读更多有关时间复杂度的内容。那里有足够多的好资源，Complexity Theory 就是其中之一。这应该可以帮助您理解为什么您的解决方案不够快。

O(n^3) 解

一种蛮力方法是检查所有可能的子数组，方法是遍历子数组的起点和终点，并将其间的所有元素相加。

给定一个大小为 n 的数组 arr，方法如下：

for (int l = 0; l < n; ++l) {
    for (int r = l; r < n; ++r) {
        long sum = 0;
        for (int pos = l; pos <= r; ++pos) {
            sum += arr[pos];
        }
        if (sum < k)
            max = Math.max(max, sum);
    }
}

最终答案存储在max。

O(n^2) 解

更快的解决方案将通过使用 prefix sums 来消除第三个循环。这可以如下完成，借助与主数组大小相同的辅助数组 preSum，其中 preSum[i] 存储前 i 个元素的总和：

preSum[0] = arr[0];
for (int i = 1; i < n; ++i)
    preSum[i] = preSum[i - 1] + arr[i];
for (int l = 0; l < n; ++l) {
    for (int r = l; r < n; ++r) {
        long sum = preSum[r];
        if (l > 0)
            sum -= preSum[l - 1];
        if (sum < k)
            max = Math.max(max, sum);
    }
}

O(n)解

这个问题最有效的解决方案是使用滑动window/双指针方法。请注意，我们假设不允许使用负数。

我们从数组开头的 l 和 r 开始。每个阶段有两种可能的情况：

当前子数组的总和<k：我们可以满怀希望地尝试向子数组中添加更多的元素。我们通过向右移动 r 一步来做到这一点。
当前子数组的和>=k：我们需要删除一些元素，使和满足给定的约束条件。这可以通过向右移动 l 一步来完成。

重复此操作，直到我们需要递增 r，但已到达数组末尾。代码看起来像这样：

long max = 0;
int l = 0;
int r = 0;
long sum = arr[0];
    while (true) {
    if (sum >= k) {
        sum -= arr[l];
        ++l;
    } else {
        if (r == n - 1)
            break;
        else {
            ++r;
            sum += arr[r];
        }
    }
    if (sum < k)
        max = Math.max(max, sum);
}

找到 n 个连续数字的最大和，其中 sum < k

Finding the max sum of n consecutive numbers where sum < k

arrays

algorithm

sum

time-complexity

max