Given an array of integers, write a function to find the contiguous subarray with the largest sum. Return the sum of that subarray.

For example:

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6

Explanation: The contiguous subarray [4, -1, 2, 1] has the largest sum = 6.

Constraints:

1. The array can contain positive, negative, and zero integers.
2. The subarray must be contiguous (elements must be adjacent).
3. If all numbers are negative, the function should return the largest negative number (or 0 if the array is empty).

Your function should be efficient and handle arrays of various sizes. Consider edge cases such as an empty array or an array with only one element.

What is the time and space complexity of your solution?

Maximum Contiguous Subarray Sum

Given an array of integers, the task is to find the contiguous subarray with the largest sum and return that sum. This problem is a classic example that can be efficiently solved using Kadane's Algorithm.

Naive Approach

A straightforward but inefficient approach is to check every possible subarray and compute its sum. We would then return the maximum sum found.

Code

def max_subarray_naive(nums):
    max_sum = float('-inf')
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            current_sum = sum(nums[i:j+1])
            max_sum = max(max_sum, current_sum)
    return max_sum

Time Complexity

The time complexity of this naive approach is O(n^2) because we have nested loops, each potentially iterating through the entire array.

Space Complexity

The space complexity is O(1) as we're only using a constant amount of extra space.

Optimal Approach: Kadane's Algorithm

Kadane's Algorithm is a dynamic programming approach to solve this problem efficiently. The main idea is to keep track of the maximum sum ending at each position and the overall maximum sum.

Code

def max_subarray_kadane(nums):
    max_so_far = float('-inf')
    current_max = 0

    for i in range(len(nums)):
        current_max += nums[i]

        if current_max > max_so_far:
            max_so_far = current_max

        if current_max < 0:
            current_max = 0

    return max_so_far

Example

Consider the array [-2, 1, -3, 4, -1, 2, 1, -5, 4].

1. Initialize max_so_far = -inf and current_max = 0.
2. Iterate through the array:
   • nums[0] = -2: current_max = -2. Since current_max > max_so_far, max_so_far = -2. Since current_max < 0, current_max = 0.
   • nums[1] = 1: current_max = 1. Since current_max > max_so_far, max_so_far = 1. Since current_max > 0, do nothing.
   • nums[2] = -3: current_max = -2. max_so_far remains 1. Since current_max < 0, current_max = 0.
   • nums[3] = 4: current_max = 4. Since current_max > max_so_far, max_so_far = 4.
   • nums[4] = -1: current_max = 3. max_so_far remains 4.
   • nums[5] = 2: current_max = 5. Since current_max > max_so_far, max_so_far = 5.
   • nums[6] = 1: current_max = 6. Since current_max > max_so_far, max_so_far = 6.
   • nums[7] = -5: current_max = 1. max_so_far remains 6.
   • nums[8] = 4: current_max = 5. max_so_far remains 6.
3. Return max_so_far = 6.

Time Complexity Analysis

The time complexity of Kadane's Algorithm is O(n) because it involves a single pass through the array.

Space Complexity Analysis

The space complexity of Kadane's Algorithm is O(1) as we're only using a constant amount of extra space to store max_so_far and current_max.

Edge Cases

1. Empty Array: If the array is empty, return 0.
2. All Negative Numbers: If the array contains only negative numbers, the function should return the largest negative number (or 0 if the array is empty).

Handling Edge Cases

def max_subarray_kadane_with_edge_cases(nums):
    if not nums:
        return 0

    max_so_far = float('-inf')
    current_max = 0
    all_negative = True

    for i in range(len(nums)):
        if nums[i] >= 0:
            all_negative = False
        current_max += nums[i]

        if current_max > max_so_far:
            max_so_far = current_max

        if current_max < 0:
            current_max = 0

    if all_negative:
        return max(nums)  # Return the largest negative number

    return max_so_far

This enhanced version covers the edge cases of an empty array and an array with all negative numbers.