Standard Bar Arrays · Medium O(n) · O(1)
A grid trader logs the net megawatt balance for each interval of the day, where selling shows as positive and drawing power shows as negative. The desk wants the most profitable contiguous block of intervals. A block must be non-empty, so a day of only losses must report the least painful single interval rather than zero.
Input: An array nums of n integers, one net balance per interval.
Output: The largest possible sum of a non-empty contiguous subarray of nums.
1 <= n <= 10^5-10^4 <= nums[i] <= 10^4Input: {"nums":[-2,1,-3,4,-1,2,1,-5,4]}
Output: 6
The block 4,-1,2,1 totals 6, and including either neighbouring negative would drag it down.
Input: {"nums":[1]}
Output: 1
A single interval is the only legal block, so its value is the answer.