Scribd
Upload
5 views1 page

ND

The document contains a Python implementation of the divide and conquer algorithm to find the maximum subarray sum. It includes functions to calculate the maximum crossing sum and the maximum subarray sum recursively. An example usage is provided, demonstrating the algorithm with a sample array.

Uploaded by

onlyfile008
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
5 views1 page

ND

The document contains a Python implementation of the divide and conquer algorithm to find the maximum subarray sum. It includes functions to calculate the maximum crossing sum and the maximum subarray sum recursively. An example usage is provided, demonstrating the algorithm with a sample array.

Uploaded by

onlyfile008
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

from math import inf

def max_crossing_sum(arr, left, mid, right):


# best sum going left from mid
best_left = -inf
cur = 0
for i in range(mid, left - 1, -1):
cur += arr[i]
if cur > best_left:
best_left = cur

# best sum going right from mid + 1


best_right = -inf
cur = 0
for i in range(mid + 1, right + 1):
cur += arr[i]
if cur > best_right:
best_right = cur

return best_left + best_right

def max_subarray_divide_conquer(arr, left, right):


# base case: one element
if left == right:
return arr[left]

mid = (left + right) // 2

# max entirely in left half


left_max = max_subarray_divide_conquer(arr, left, mid)
# max entirely in right half
right_max = max_subarray_divide_conquer(arr, mid + 1, right)
# max crossing the midpoint
cross_max = max_crossing_sum(arr, left, mid, right)

return max(left_max, right_max, cross_max)

def max_subarray_sum(arr):
if not arr:
raise ValueError("Array must not be empty")
return max_subarray_divide_conquer(arr, 0, len(arr) - 1)

# example
if __name__ == "__main__":
nums = [2, -3, 6, -5, 4, 2]
print(max_subarray_sum(nums)) # prints 7

You might also like