Kadane's Algorithm

Kadane's Algorithm is used to find the contiguous subarray within a one-dimensional array of numbers that has the largest sum.

Naive Approach#

A naive approach to solve this problem would involve checking all possible subarrays and calculating their sums, resulting in a time complexity of O(n^2).

Kadane's Algorithm optimizes this by solving the problem in linear time, O(n), making it highly efficient for large datasets.

Kadane's Algorithm#

Kadane's Algorithm works by iterating through the array and keeps track of two variables:

• current_max: The maximum sum of the subarray that ends at the current position.
• global_max: The overall maximum sum found so far across all subarrays.

At each step, the algorithm decides whether to:

• Extend the current subarray by adding the current element.
• Start a new subarray beginning with the current element.

The choice depends on which option yields a higher sum.

Code#

from typing import List

def max_subarray(arr: List[int]) -> int:
    current_max = arr[0]
    overall_max = arr[0]

    for i in range(1, len(arr)):
        current_max = max(arr[i], current_max + arr[i])
        overall_max = max(overall_max, current_max)

    return overall_max


arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = max_subarray(arr) # 6

# The maximum contiguous subarray in the given array is [4, -1, 2, 1], 
# with a sum of 6.
print("Maximum contiguous subarray sum:", max_sum)