Maximum Subarray

This problem asks you to find the contiguous subarray within a given array of integers that has the largest sum. This is a classic problem in computer science with applications in fields like finance (analyzing stock prices) and signal processing (finding peaks in data). Successfully solving this problem demonstrates understanding of dynamic programming and efficient algorithm design.

Problem Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A contiguous subarray is a subarray where the elements are adjacent in the original array.

What needs to be achieved:

• Identify the subarray within nums that yields the maximum sum when its elements are added together.
• Return the sum of the elements in that maximum subarray.

Key Requirements:

• The subarray must be contiguous (elements must be next to each other in the original array).
• The subarray must contain at least one element.
• The input array nums can contain positive, negative, and zero values.

Expected Behavior:

The function should iterate through the input array and efficiently determine the maximum subarray sum. It should handle cases with all negative numbers, all positive numbers, and mixed positive and negative numbers.

Edge Cases to Consider:

• Empty Array: While the problem states the subarray must contain at least one number, consider how your solution handles an empty input array (though it's not explicitly required).
• All Negative Numbers: The maximum subarray will be the single element with the largest value (least negative).
• Single Element Array: The maximum subarray is simply the single element.
• Large Arrays: Efficiency is important; avoid brute-force approaches that have quadratic time complexity.

Examples

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
Explanation: The single element is the maximum subarray.

Example 3:

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

Example 4:

Input: [-1,-2,-3]
Output: -1
Explanation: The single element -1 has the largest sum.

Constraints

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• The solution should have a time complexity of O(n), where n is the length of the input array. A brute-force O(n^2) solution will likely fail the performance constraints.

Notes

Consider using Kadane's Algorithm, a dynamic programming approach, to solve this problem efficiently. The core idea is to maintain a "current maximum" and a "global maximum" as you iterate through the array. Think about how the current maximum can be updated based on the current element and the previous current maximum. Don't focus on finding the subarray itself, only the sum.

Pseudocode:

function maxSubarraySum(nums):
  max_so_far = nums[0]  // Initialize global maximum to the first element
  current_max = nums[0] // Initialize current maximum to the first element

  for i from 1 to nums.length - 1:
    current_max = max(nums[i], current_max + nums[i]) // Decide whether to start a new subarray or extend the current one
    max_so_far = max(max_so_far, current_max) // Update the global maximum if the current maximum is larger

  return max_so_far