c++ - 如何最有效地增加大型数组中指定范围内的值，然后找到最大值

Question

所以我刚刚参加了面试的编程测试，我认为自己是一个不错的程序员，但是我无法满足在线测试的时间限制(并且不允许调试器)。本质上，问题是给出一系列索引 [low, high] 和一个将这些索引增加的值，在对数组执行 M 次后，找到最大值。

So if you had an array of size 5 [0, 0, 0, 0, 0]
and you were given instructions
[0, 3] 143
[2, 4] 100
and [2,2] 100
the array would be [143, 143, 343, 243, 100]

最高为 343。

我尝试了天真的解决方案，但想不出一个巧妙的算法，并认为答案必须通过一些内存复制来完成？

如何才能最快地解决这个问题？我在这里遗漏了什么吗？

谢谢

Answer 1

从你质疑大数组是否在开始时全为零，或者是否给你一个带有初始值的大数组，这并不完全清楚，但在这两种情况下都可以使用类似的方法:

A) 大量的零

首先，在这种情况下，不需要实际创建大数组，也不需要对其进行任何操作。

给定这些范围和值:

[0, 3] 143
[2, 4] 100
[2, 2] 100

创建一个列表，其中每个低索引与值一起存储，每个高索引(加 1)与值的倒数一起存储:

{0, +143} {4, -143} {2, +100} {5, -100} {2, +100} {3, -100}

然后对这个列表进行排序(最好合并具有相同索引的值):

{0, +143} {2, +200} {3, -100} {4, -143} {5, -100}

然后，遍历列表，保持总计，并找到最大值及其开始和结束索引:

           total  
{0, +143}   143  
{2, +200}   343   <-- max  
{3, -100}   243   <-- end  
{4, -143}   100  
{5, -100}     0  

所以最大值是 343，它的范围是索引 2 ~ 3(所以真的只有位置 2)。

该算法的复杂度与范围数M成线性关系，但不受大数组N大小的影响，所以O(M)。

B) 具有初始值的大数组

如果给定一个包含初始值的数组，例如:

[300, 200, 400, 600, 700]

任何元素在范围内的值增加后仍可能具有最大值，因此最后您必须遍历数组中的每个元素以找到最大值。

但是，您可以通过创建与上面相同的列表来避免实际增加数组中的任何值，或多次迭代数组:

{0, +143} {2, +200} {3, -100} {4, -143} {5, -100}

然后遍历数组以找到最大值，同时保留附加值的运行总和，并将这些添加到值中同时与最大值进行比较:

              total
0: {0, +143}   143   value: 300 + 143 = 443  
1: no change   143   value: 200 + 143 = 343  
2: {2, +200}   343   value: 400 + 343 = 743  
3: {3, -100}   243   value: 600 + 243 = 843   <-- max  
4: {4, -143}   100   value: 700 + 100 = 800   <-- end  
5: {5, -100}     0  

所以最大值是 843，它的范围是索引 3 ~ 4(所以实际上只有位置 3)。

该算法的复杂度与大数组N的大小成线性关系，与范围数M成线性关系，即O(N+M)，但假设N远大于M，这就是~O (N).