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