Rune River Gold Rush

The Rune River flows through the valley, carrying gold nuggets along its path. Each nugget has a value (positive or negative ÔÇö some are fool's gold that cost energy to collect). A miner can choose any contiguous segment of the river to pan for gold. Given an array of numbers representing gold values along the river, find the maximum sum of any contiguous subarray. The miner can also choose to pan nothing, in which case the sum is 0. Solve this in O(n) time.