Algorithm of the day -

The Algorithm for Finding the Maximum Subarray

Summary

This algorithm finds the maximum contiguous subarray within a one-dimensional array of numbers.

Use Case

For example, given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the maximum subarray is [4, -1, 2, 1] with a sum of 6.

Steps

  1. Initialize the maximum sum and the current sum to the first element of the array.
  2. Iterate through the array starting from the second element.
  3. For each element, calculate the current sum by adding the current element to the previous sum.
  4. If the current sum is less than the current element, update the current sum to the current element.
  5. If the current sum is greater than the maximum sum, update the maximum sum to the current sum.
  6. Return the maximum sum.

Complexity

The time complexity of this algorithm is O(n) and the space complexity is O(1), where n is the number of elements in the array.

Code Example

def max_subarray(arr):
    max_sum = float('-inf')
    current_sum = 0
    for num in arr:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum