连续子数组求和优化

Question

连续子数组求和优化

3

我正在解决一个问题，其中我有一个数组和两个给定的索引min和max，我需要找到它们之间所有连续子数组的和。

我能想到的只有这个O(n^2)的代码。

for (int i = min; i <= max; ++i)
{
    long long sum = 0;
    for (int j = i; j <= max; ++j)
    {
        sum += a[j];
        printf("%lld\n", sum);
    }
}

有人可以帮我优化这段代码吗？

- vinay_Kumar

1

您是否正在寻找 std::partial_sum 函数？ - Wintermute

1

这是C还是C++，它们不一样。 - Iharob Al Asimi

@OllieFord，你能给出一个它无法识别的样例吗？我找不到这样的情况。 - vinay_Kumar

“所有子数组的和”是一个总共一个数字。如果您需要每个子数组一个数字，那就是“所有子数组的总和”。决定您想要什么。 - n. m.

这可能是因为今天是周一早上，而且对我来说是新年的第一天，但你正在做的相当于计算最小值和最大值之间所有值的总和，然后简单地迭代通过减去当前索引处的值（从上一个总和中）来给出以下值的总和？ - Nim

1

@n.m. 我认为“每个的总和”是最清晰的语言 - OP说明代码可以工作，因此这显然是意图。Vinay - 抱歉，我错了，它没有错过我想到的情况。 - OJFord

4个回答

2

没有更快的解决方案。

由于您的输出大小为O（n²），因此没有算法可以更快。

- Hans Klünder

如果我不需要为每个总和打印，但需要检查某些条件怎么办？ - vinay_Kumar

闪烁的灯光完全正确！除了结果错误之外，如果您想检查O(n^2)的结果，您不会比O(n^2)更快。也许您可以优化检查以使其尽可能快，但是没有办法将其改进为类似于O(nlogn)的东西。 - Hans Klünder

1

可以通过仔细地记忆部分和来改进。 - OJFord

这是dasblinkenlight写的：一个优化正确的实现是O(n^2)。 - Hans Klünder

2

当max-min+1等于n时，需要打印n(n-1)/2个和。这是O(n²)个值。要生成O(n²)个值的最快算法的时间复杂度为O(n²)，因此您的解决方案已经是最优的。

- Sergey Kalinichenko

0

对于超大的计算块或像实时数据分析之类的任务，由于数组内容不会改变，您可以在并行线程中进行计算。

对于一般情况，只需循环它们并让编译器展开并使用矢量化指令即可。

- Non-maskable Interrupt

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aybassiouny · Accepted Answer

使用动态规划，可以实现O(n)的答案。基本思想是计算所有元素的累积前缀和。

设 A(i) 为元素从0到i的总和。这可以通过以下方法轻松地以O(n)的时间复杂度计算：

// let your array by Src[Max]
int A[MAX];
A[0] = Src[0];
for(int i=1; i<MAX; i++) A[i] +=A[i-1] + (i+1)*Src[i];

然后对于任何元素i和j，你可以计算sum(i,j) = A[j] - A[i]（根据输入要求进行边界调整）。