Given an array of integers arr, return the maximum sum of any contiguous subarray within arr. The subarray must be non-empty.
Example 1
Input: [3, -1, 2, -1, 6, -5]
Output: 9
Explanation: The subarray [3, -1, 2, -1, 6] has the largest sum 9.
Example 2
Input: [-5, -2, -3, -1]
Output: -1
Explanation: The subarray [-1] has the largest sum -1.
Example 3
Input: [7, -2, 5, -1, 2]
Output: 11
Explanation: The subarray [7, -2, 5, -1, 2] has the largest sum 11.
Constraints
Case 1
Input: [2, -3, 4, -1, 2, 1, -5, 3]
Expected: 6
Case 2
Input: [10, -2, -3, 4, -1, 2, 1, -5, 4]
Expected: 11
Case 3
Input: [-1, -2, -3, -4]
Expected: -1
Case 4
Input: [1, 2, 3, 4, 5]
Expected: 15
Case 5
Input: [-2, 1, -3, 5, -1, 2, 1, -5, 4]
Expected: 7