Maximum Subarray Sum

This challenge focuses on finding the contiguous subarray within a given array of numbers that has the largest sum. This is a fundamental problem in computer science with applications in areas like financial analysis (identifying periods of maximum profit) and signal processing.

Problem Description

Given an array of integers, nums, your task is to find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Key Requirements:

• The subarray must be contiguous, meaning its elements must be adjacent in the original array.
• The subarray must contain at least one number.
• You need to return the sum of this maximum subarray, not the subarray itself.

Expected Behavior:

• For any given array of integers, your algorithm should correctly identify the subarray with the greatest possible sum and return that sum.

Edge Cases to Consider:

• An array containing only positive numbers.
• An array containing only negative numbers.
• An array containing a mix of positive and negative numbers.
• An array with a single element.

Examples

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum = 1.

Example 3:

Input: nums = [5, 4, -1, 7, 8]
Output: 23
Explanation: The subarray [5, 4, -1, 7, 8] has the largest sum = 23.

Example 4:

Input: nums = [-1, -2, -3, -4]
Output: -1
Explanation: The subarray [-1] has the largest sum = -1. (Since it must contain at least one number)

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• The input nums will always be a non-empty array of integers.
• Your solution should aim for an efficient time complexity.

Notes

Consider how to handle negative numbers. An intuitive approach might be to sum up all positive numbers, but this won't work if a sequence of negative numbers is surrounded by large positive numbers that would be better off excluded. Think about how to track the "current best" sum as you iterate through the array.