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)