c++ - How to most efficiently increase values at a specified range in a large array and then find the largest value -

so had programming test interview , consider myself decent programmer, unable meet time constraints on online test (and there no debugger allowed). question give range of indices [low, high] , value increase these indices by, after doing m times array, find me largest value.

so if had array of size 5 [0, 0, 0, 0, 0] , given instructions [0, 3] 143 [2, 4] 100 , [2,2] 100 array [143, 143, 343, 243, 100] 

and highest 343.

i tried naive solution couldnt think of slick algorithm , thought answer had done memory copying?

how 1 solve issue fastest? there missing here?

thanks

it isn't clear question whether large array contains zeros @ start, or whether given large array initial values, similar methods can used in both cases:

a) large array of zeros

first of all, in case there no need create large array, or it.

given these ranges , values:

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

create list, every low index stored value, , every high index (plus 1) stored inverse of value:

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

then sort list (and preferably merge values same index):

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

then, iterate on list, keep running total, , find maximum value , start , end index:

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

so maximum value 343, , range index 2 ~ 3 (so position 2).

the complexity of algorithm linear number of ranges m, not influenced size of large array n, o(m).

b) large array initial values

if given array inital values, e.g.:

[300, 200, 400, 600, 700]

any element still have largest value after values in ranges have been increased, in end have iterate on every element in array find maximum value.

however, can avoid having increase values in array, or iterate on array more once, creating same list above:

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

and iterating on array find maximum value, while keeping running total of additional values, , adding these values while comparing 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   

so maximum value 843, , range index 3 ~ 4 (so position 3).

the complexity of algorithm linear size of large array n, , linear number of ranges m, or o(n+m), assuming n greater m, ~ o(n).