Maximum Subarray Sum

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Examples

maxSubArray([1, -2, 5, -4, 5]);
// returns 6
// The maximum sum can be found in the subarray [5, -4, 5]
// 5 + (-4) + 5 = 6

maxSubArray([-10,-5,-6,-8,-1])
// returns -1
// The least negative number forms the subarray with maximum sum.

Time Complexity

Can you figure out the O(n) solution?