如何在大型数组中最有效地增加指定范围内的值，然后找到最大值 [英] How to most efficiently increase values at a specified range in a large array and then find the largest value
问题描述
因此，我刚刚进行了一次面试的编程测试，我认为自己是一个不错的程序员，但是我无法满足在线测试的时间限制（并且不允许调试器使用）。本质上，问题是给出一个范围为[低，高]的索引，并给出一个值来增加这些索引，方法是对数组进行M次运算后，找到最大值。
So I just had a programming test for an interview and I consider myself a decent programmer, however I was unable to meet time constraints on the online test (and there was no debugger allowed). Essentially the question was give a range of indices [low, high] and a value to increase these indices by, after doing this M times to the array, find me the largest value.
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。
我尝试过幼稚的解决方案，但无法想到灵巧的算法，并认为答案必须通过某些内存复制来完成？
I tried the naive solution but couldnt think of a slick algorithm and thought the answer had to be done by some memory copying?
如何才能最快解决这一问题？
How could one solve this issue the fastest? Is there something i am missing here?
谢谢
推荐答案
它您是否还不确定大型数组在开始时是否包含全零，或者是否为您提供了具有初始值的大型数组，但在两种情况下都可以使用类似的方法：
It isn't completely clear from you question whether the large array contains all zeros at the start, or whether you are given a large array with initial values, but similar methods can be used in both cases:
A）大的零数组
首先，在这种情况下，无需实际创建大的零数组，或对其进行任何处理。
First of all, in this case there is no need to actually create the large array, or do anything with it.
给出以下范围和值：
[0，3] 143 < br>
[2，4] 100
[2，2] 100
[0, 3] 143
[2, 4] 100
[2, 2] 100
创建一个列表，其中每个低索引都存储有该值，每个高索引（加1）都存储有该值的倒数：
Create a list, where every low index is stored with the value, and every high index (plus 1) is stored with the inverse of the value:
{0，+143} {4，-143} {2，+100} {5，-100} {2，+100} {3，-100}
{0, +143} {4, -143} {2, +100} {5, -100} {2, +100} {3, -100}
然后对该列表进行排序（最好合并具有相同索引的值）：
Then sort this list (and preferably merge values with the same index):
{0， +143} {2，+200} {3，-100} {4，-143} {5，-100}
{0, +143} {2, +200} {3, -100} {4, -143} {5, -100}
然后，遍历列表，保持运行总计，并找到最大值及其开始和结束索引：
Then, iterate over the list, keep a running total, and find the maximum value and its start and end index:
total
{0, +143} 143
{2, +200} 343 <-- max
{3, -100} 243 <-- end
{4, -143} 100
{5, -100} 0
因此最大值为343，其范围为索引2〜3（因此实际上仅是位置2）。
So the maximum value is 343, and its range is index 2 ~ 3 (so really only position 2).
此算法的复杂度与范围M呈线性关系，但不受大型数组N的大小影响，因此为O（M）。
The complexity of this algorithm is linear to the number of ranges M, but not influenced by the size of the large array N, so O(M).
B）具有初始值的大型数组
如果给定一个数组带有初始值，例如：
If you are given an array with inital values, e.g.:
[300，200，400，600，700]
[300, 200, 400, 600, 700]
在范围中的值增加之后，任何元素仍然可以具有最大值，因此最后您必须遍历数组中的每个元素以找到最大值。
any element could still have the largest value after the values in the ranges have been increased, so in the end you have to iterate over every element in the array to find the maximum value.
但是，通过创建与上面相同的列表，您可以避免实际增加数组中的任何值，或者避免多次遍历数组：
However, you can avoid having to actually increase any values in the array, or iterate over the array more than once, by creating the same list as above:
{0，+143} {2，+200} {3，-100} {4，-143} {5，-100}
{0, +143} {2, +200} {3, -100} {4, -143} {5, -100}
，然后遍历数组以查找最大值，同时保持附加值的总和，并将这些值相加而与最大值进行比较：
and then iterating over the array to find the maximum value, while keeping a running total of the additional values, and adding these to the values while comparing with the maximum value:
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）。
So the maximum value is 843, and its range is index 3 ~ 4 (so really only position 3).
此算法的复杂度与大数组N的大小呈线性关系，与范围M或O（N + M）的数目呈线性关系，但假设N比M大得多，这是〜O（N）。
The complexity of this algorithm is linear to the size of the large array N, and linear to the number of ranges M, or O(N+M), but assuming that N is much greater than M, this is ~ O(N).
这篇关于如何在大型数组中最有效地增加指定范围内的值，然后找到最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
