Algorithms

Peak memory from an allocation log

Peak memory from an allocation log

A profiler writes one line every time your program asks for memory or gives some back. You are handed that log as a list of whole numbers: a positive entry means that many cells were taken, a negative entry means that many were released, and a zero means nothing happened.

What matters for a memory limit is not the total ever taken but the largest amount held at one moment. Write peak_cells(events), which returns that peak. The program starts holding nothing.

Worked example: with events = [5, 3, -4, 6] the amount held goes 5, then 8, then 4, then 10. The largest of those is 10, so the answer is 10. Note that 5 plus 3 plus 6, which is 14, is the total ever taken and is not the answer.

  • Constraints: the log has between 0 and 100000 entries, and each entry is between -1000000 and 1000000.
  • The log is valid: the amount held never goes below zero.
  • An empty log means nothing was ever held, so the answer is 0.
  • The answer can be as large as about 10^11, which does not fit in a 32-bit integer. Use a 64-bit type.
Code

Run your code to see how it does on the examples. Submit also runs the hidden cases.