13: Maximum subarray

Given an array of integers, find the contiguous subarray which has the largest sum, return its sum

 

Example 1

Input: [-4, 1, 2, -3, 1]

Output: 3

Explanation: [1, 2] is the subarray with the largest sum 3

Example 2

Input: [1, 1, 2, 5]

Output: 9