Maximum Subarray

Problem

Given an array of integers, find a contiguous subarray which has the largest sum.

Example

Given the array [-2,2,-3,4,-1,2,1,-5,3], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Note

The subarray should contain at least one number.

Challenge

Can you do it in time complexity O(n)?