找到 n 个连续数字的最大和,其中 sum < k
Finding the max sum of n consecutive numbers where sum < k
我得到一个数组,要求我找出 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
循环完成了,但是太花时间了,有没有其他方法可以让这个程序运行?)
基础
首先,我建议您阅读更多有关时间复杂度的内容。那里有足够多的好资源,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
个连续数字的最大可能总和,其中最大总和小于给定值 k
。
例如:
array = {1, 3, 1, 2, 3, 4, 1}
k = 7
这里,答案一定是6,因为我们可以得到的最大和是小于7的是:arr[1] + arr[2] + arr[3] = 3 + 1 + 2 = 6
我如何编写算法来找到这样的值?
(我已经用嵌套的for
循环完成了,但是太花时间了,有没有其他方法可以让这个程序运行?)
基础
首先,我建议您阅读更多有关时间复杂度的内容。那里有足够多的好资源,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);
}