5. Maximum Subarray

Easy · Array

Find the maximum sum of any contiguous subarray. You're given an array of integers, and you need to find a continuous sequence of elements whose sum is as large as possible. Return that maximum sum. For example, in the array [-2,1,-3,4,-1,2,1,-5,4], the subarray [4,-1,2,1] has the largest sum of 6.

Examples

Example 1
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: Subarray [4,-1,2,1] sums to 6
Example 2
Input: [1]
Output: 1
Explanation: Single element is itself the max sum

Constraints