在HackerRank的Array Manipulation背后使用的逻辑

Question

我无法掌握Hackerrank这个问题解决方案背后的逻辑,https://www.hackerrank.com/challenges/crush/problem

在讨论部分,许多人也发布了他们的解决方案,但我无法理解为什么这种逻辑有效.

以下解决方案取自相同问题的讨论部分,并具有最大数量的upvotes,

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    long int N,K,p,q,sum,i,j,max=0,x=0;

    cin>>N>>K;
    long int *a=new long int[N+1]();

    for(i=0;i<K;i++)
    {
        cin>>p>>q>>sum;
        a[p]+=sum;
        if((q+1)<=N) a[q+1]-=sum;
    }

    for(i=1;i<=N;i++)
    {
       x=x+a[i];
       if(max<x) max=x;

    }

    cout<<max;
    return 0;
}

有人可以解释背后的逻辑吗？非常感谢您的帮助.

Answer 1

我们基本上将增量存储在范围中的起始和最后一个元素之后.因为a b k我们将增加+k索引中的所有元素,[a,b]但接下来的元素将不会增加.所以我们减去它,因为在前一个增量中,范围右边的所有元素都会减少-k.我们基本上通过这个增量/减量存储所有最终值.

最后,我们正在从左到右计算元素.如果你想得更深一点,那就是存储一个元素比前一个元素大一些.

最初阵列将是0 0 0 0 0.

在第一次操作之后,1 3 3数组元素应该是, 3 3 3 0 0但我们正在这样存储它

3 0 0 -3 0

含义

First element is 3 greater than 0.
Second  ->       0 greater than index 1 element.
Third   ->       0 greater than index 2 element
Fourth  ->      -3 greater than index 3 element.
fifth   ->       0 greater than index 4 element.

在第二次操作之后,2 4 4最初的数组将是,3 7 7 4 0但我们这样存储它3 4 0 -3 -4.就像我详细描述的那样,请记住并以这种方式思考,你会发现我们并没有丢失信息.我们只是以不同的方式存储它.

最终价值将是

0+(3) 0+3+(4) 0+3+4+(0) 0+3+4+0+(-3) 0+3+4+0-3+(-4)

3  7    7       4           0  matches with what we got earlier.

注意我们如何计算每个元素.只需添加前一个元素,其中当前元素的值更大.

请注意,此解决方案有效,因为仅查询一次.如果它被查询m次数,那么这个消息不起作用.然后你将不得不深入挖掘a b k或使用+k.

Answer 2

我将尝试解释我对此的理解：
每行输入基本上描述了一个序列，并且要求您找到这些序列之和的最大值。
例如，如果N给出为5：
行2 4 13描述序列[0, 13, 13, 13, 0]
行3 5 11描述序列[0, 0, 11, 11, 11]。
如果这些是唯一的行，我们从两者的逐点总和中得到结果序列，即[0, 13, 24, 24, 11]。

现在，我们可以描述上面的序列另一种方式是由差序列，即在指数i我们将继续在指标元素之间的差别i，并在索引中的元素i-1，我们可以通过差的运行总和得到原始序列序列。

在上述序列的情况下，差分序列为：
[0, 13, 0, 0, -13]对于描述2 3 13
[0, 0, 11, 0, 0]的序列3 5 11
[0, 13, 11, 0, -13对于描述的序列 对于序列的总和。

一个重要的性质是序列之和的差分序列是差分序列之和。

因此，对于每一行，解决方案所做的是对差异序列求和（由于序列的性质，它最多只需要 2 次操作），然后找到最大值，它需要差异序列的运行总和，从而得到序列的元素，并保存该运行总数的最大值。

虽然我给出的例子只有 2 行，但同样的想法适用于任意数量的行。

我希望这对解决方案背后的想法给出了很好的直觉。

Answer 3

这两个地方帮助我更清楚地理解了这个算法。 Prefix_sum_array_and_difference_array
堆栈溢出

如果你想要一个简单直接的解释：初始，数组是 0 0 0 0 0 cpp after the first operation, 1 2 100 it will become seq1: 100 100 0 0 0 and after second 2 5 100 seq2: 0 100 100 100 100 and after 3 4 100 seq2: 0 0 100 100 0 但是当我们在每一步应用差异数组时，我们会得到

cpp diff seq of seq1: 100 0 -100 0 0 diff seq of seq2: 0 100 0 0 0 -100 diff seq of seq3: 0 0 100 0 -100

一个重要的性质是序列之和的差分序列是差分序列之和。

它会给我们， cpp 100 100 0 0 -100 -100(for clarity purpose only) 或者您可以添加所有序列 cpp seq1+seq2+seq3 = 100 200 200 200 100 ，然后找到差异 seq 或差异数组，即 100 100 0 0 -100，然后找到前缀数组。

为什么我们忽略前100个？？？阅读第一篇关于差分数组和前缀和数组的文章！！！！

在此之后，做 prefix sum cpp 100 200 200 200 100 0 Ignore last 0 因为我们考虑的最后一个索引只是为了清楚起见。

所以，这两个步骤都为我们找到了差异数组:) cpp a[p]+=sum; if((q+1)<=N) a[q+1]-=sum;