Maximum Subarray Sum

Brute Force Solution

A naive approach would be to iterate through all possible subarrays, calculate their sums, and keep track of the maximum sum encountered. This involves two nested loops:

1. The outer loop determines the starting index of the subarray.
2. The inner loop determines the ending index of the subarray.

Code Example (Python):

def max_subarray_brute_force(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: O(n^2) due to the nested loops. The sum() function inside the inner loop also takes O(n) in the worst case, making it technically O(n^3). However, the dominant factor is still O(n^2) because the sum can be calculated incrementally.

Space Complexity: O(1) as it uses only a constant amount of extra space.

Optimal Solution (Kadane's Algorithm)

Kadane's Algorithm provides an efficient way to solve this problem in linear time. The idea is to maintain two variables:

1. max_so_far: Stores the maximum sum found so far.
2. current_max: Stores the maximum sum ending at the current position.

For each element in the array, we update current_max by either starting a new subarray from the current element or extending the previous subarray by adding the current element. We then update max_so_far with the maximum of max_so_far and current_max.

Code Example (Python):

def max_subarray_kadane(nums):
    max_so_far = float('-inf')
    current_max = 0
    for i in range(len(nums)):
        current_max = max(nums[i], current_max + nums[i])
        max_so_far = max(max_so_far, current_max)
    return max_so_far

Time Complexity: O(n) as it iterates through the array only once.

Space Complexity: O(1) as it uses only a constant amount of extra space.

Edge Cases

• Empty array: While the problem states 1 <= nums.length <= 10^5, it's good to consider what should happen with an empty array. You might throw an exception or return 0. The provided code will actually still work because it would not execute the loop, and the initial value of max_so_far (negative infinity) will be returned, which is not ideal. It would be better to check for len(nums) == 0 and return 0 or throw an exception.
• All negative numbers: The algorithm correctly handles this case because max_so_far is initialized to negative infinity, and it will find the least negative number (i.e., the largest number) in the array.
• Single element array: The algorithm correctly returns the value of that single element.

Divide and Conquer (Follow-up)

While Kadane's algorithm is generally preferred for its simplicity and efficiency, the divide and conquer approach offers an alternative perspective.

1. Divide: Split the array into two halves.
2. Conquer: Recursively find the maximum subarray sum in each half.
3. Combine: The maximum subarray sum is either entirely within the left half, entirely within the right half, or crosses the midpoint. We need to consider the case where the maximum subarray crosses the midpoint.

The maximum subarray sum crossing the midpoint can be found by:

• Finding the maximum subarray sum ending at the midpoint in the left half.
• Finding the maximum subarray sum starting at the midpoint + 1 in the right half.
• Adding these two sums together.

The final result is the maximum of the three sums (left half, right half, crossing the midpoint).

Time Complexity: O(n log n)

Space Complexity: O(log n) due to the recursive calls.