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 sum3
Example 2
Input: [1, 1, 2, 5]
Output: 9