Maximum Contiguous Subarray

Given an array $a_1,a_2,\dots ,a_n$ of integers (possibly negative), find the maximum sum of any contiguous subarray $a_i+a_{i+1}+\cdots +a_j$ for $1\le i\le j\le n$.

For example, for $[-2,1,-3,4,-1,2,1,-5,4]$ the answer is $6$ (subarray $[4,-1,2,1]$).

Give an $\mathcal{O}(n)$ algorithm.