I have a question: Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.
Given some queries in the form (a,b,k):
((1,5,3),(4,8,7),(6,9,1))
Add the values of k between the indices a and b inclusive:
(0,0,0, 0, 0,0,0,0,0, 0)
(3,3,3, 3, 3,0,0,0,0, 0)
(3,3,3,10,10,7,7,7,0, 0)
(3,3,3,10,10,8,8,8,1, 0)
And then return the max value which is 10
My attempt is:
from itertools import accumulate
def Operations(size, Array):
values = (0) * (size+2)
for a,b,k in Array:
values(a) += k
values(b+1) -= k
values = list(accumulate(values))
Result = max(values)
return Result
def main():
nm = input().split()
n = int(nm(0))
m = int(nm(1))
queries = ()
for _ in range(m):
queries.append(list(map(int, input().rstrip().split())))
result = Operations(n, queries)
if __name__ == "__main__":
main()
This code works, however, hits runtime errors when the arrays get too large. I have no idea how to lower the runtime further.
Example input is as follows:
5 3
1 2 100
2 5 100
3 4 100