Max SubArray

Given an integer array nums, find the contiguous subarray which has the largest sum and return its sum.

This is known as Kadane's Algorithm. You must solve it in O(n) time.

Example Inputs & Outputs

// Example 1:
Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

// Example 2:
Input: [1]
Output: 1

// Example 3:
Input: [5,4,-1,7,8]
Output: 23

Constraints & Edge Cases

• Array may contain both positive and negative numbers
• Single element array should return that element
• If all numbers are negative, return the largest among them
• Empty array should return -Infinity