Discussions

Simple approach explained for beginners. A single pass with a running value is enough here. Keep track of the best answer so far and update it as you scan, which gives O(n) time and O(1) extra space.