[Solved] Algorithm for understanding behavior of arrays [duplicate]

Basically it stores deltas rather than the final list; that means each operation only takes 2 reads and writes rather than (b – a + 1). Then the final max scan adds the deltas as it goes along, which is still an O(n) operation which you would have had to do anyway.

n, inputs = [int(n) for n in input().split(" ")]

Get the list size (n) and number of operations (m), ie 5 and 3

list = [0]*(n+1)

Create an empty 0-filled list. Should be lst = [0] * n (do not use list as a variable name, it shadows the built-in type) (we do not need an extra end cell, except as a checksum on our algorithm – if it works properly the final checksum should be 0).

for _ in range(inputs):
    x, y, incr = [int(n) for n in input().split(" ")]

Get an operation (a, b, k) ie 1, 2, 100.

    list[x-1] += incr

Add delta to the starting cell

    if((y)<=len(list)): 
        list[y] -= incr

Subtract the delta from the ending cell (should be if y < n: lst[y] -= incr)

The algorithm may be easier to understand if you add a print(lst) here (after the if but inside the for loop).

Now process the deltas to find the maximum item:

max = x = 0
for i in list:
    x=x+i;

x is now the value the actual value of the current list cell. Also max is a terrible variable name because it shadows the built-in max() function.

    if(max<x):max=x

Keep a running max tally

print(max)

Show the result.