Find Largest Sum Contiguous Subarray

Understanding the Problem

The goal is to find the subarray with the maximum sum in a given array using different methods.

Method 1: Kadane's Algorithm

This method efficiently finds the largest sum contiguous subarray using dynamic programming.

def max_subarray_sum(arr):
    max_so_far = arr[0]
    max_ending_here = arr[0]
    for i in range(1, len(arr)):
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

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

Output:

Maximum contiguous sum: 6

Method 2: Divide and Conquer

This method finds the largest sum subarray by dividing the array into halves recursively.

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]
n = len(arr)
print("Maximum contiguous sum:", max_subarray_sum(arr, 0, n - 1))
            

Output:

Maximum contiguous sum: 7

Method 3: Brute Force

This method checks all subarrays and computes their sums to find the maximum sum.

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

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

Output:

Maximum contiguous sum: 6