Kadane’s Algorithm

Understanding the Problem

The goal is to find the maximum sum of a contiguous subarray in a given array using Kadane's Algorithm.

Method 1: Kadane’s Algorithm

This method efficiently finds the maximum sum subarray in O(n) time.

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

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum sum subarray:", kadane_algorithm(arr))
            

Output:

Maximum sum subarray: 6

Method 2: Brute Force Approach

This method checks all possible subarrays and calculates their sums, leading to an O(n²) complexity.

def brute_force_max_subarray(arr):
    max_sum = float('-inf')
    for i in range(len(arr)):
        sum_ = 0
        for j in range(i, len(arr)):
            sum_ += arr[j]
            max_sum = max(max_sum, sum_)
    return max_sum

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum sum subarray:", brute_force_max_subarray(arr))
            

Output:

Maximum sum subarray: 6

Method 3: Divide and Conquer Approach

This method uses recursion to divide the array and find the maximum sum subarray.

def max_crossing_sum(arr, l, m, h):
    left_sum = float('-inf')
    sum_ = 0
    for i in range(m, l-1, -1):
        sum_ += arr[i]
        left_sum = max(left_sum, sum_)
    
    right_sum = float('-inf')
    sum_ = 0
    for i in range(m + 1, h + 1):
        sum_ += arr[i]
        right_sum = max(right_sum, sum_)
    
    return max(left_sum + right_sum, left_sum, right_sum)

def max_subarray_sum(arr, l, h):
    if l == h:
        return arr[l]
    m = (l + h) // 2
    return max(max_subarray_sum(arr, l, m),
               max_subarray_sum(arr, m+1, h),
               max_crossing_sum(arr, l, m, h))

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum sum subarray:", max_subarray_sum(arr, 0, len(arr) - 1))
            

Output:

Maximum sum subarray: 6