如何在大型数组中最有效地增加指定范围内的值，然后找到最大值
因此，我刚刚接受了一次编程测试以进行面试，我认为自己是一个不错的程序员，但是我无法满足在线测试的时间限制（并且不允许调试器使用）。本质上，问题是给出一个范围为[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。
我尝试过幼稚的解决方案，但是想不出一个灵巧的算法，以为答案必须通过一些内存复制来完成？
如何最快解决这个问题？我在这里缺少什么吗？
谢谢
回答：
对于您是否怀疑大型数组在开始时是否包含全零，或者是否为您提供了具有初始值的大型数组，您还不确定，但是在两种情况下都可以使用类似的方法：
首先，在这种情况下，无需实际创建大型数组，也无需执行任何操作。
给定以下范围和值：
[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）。
如果为您提供了具有初始值的数组，例如：
[300、200、400、600、700]
在范围内的值增加之后，任何元素仍可能具有最大值，因此最后您必须遍历数组中的每个元素以找到最大值。
但是，通过创建与上述相同的列表，可以避免必须实际增加数组中的任何值，或者避免多次遍历数组的情况：
{0，+143} {2，+200} {3，-100} {4，-143} {5，-100}
然后遍历数组以找到最大值，同时保持其他值的总和，并在与最大值进行比较的同时将这些值添加到这些值中：
total0: {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） 。
以上是 如何在大型数组中最有效地增加指定范围内的值，然后找到最大值 的全部内容， 来源链接： utcz.com/qa/406085.html
