Solves the maximum subarray problem using divide and conquer. :param arr: the given array of numbers :param low: the start index :param high: the end index :return: the start index of the maximum subarray, the end index of the maximum subarr
(
arr: Sequence[float], low: int, high: int
)
| 17 | |
| 18 | |
| 19 | def max_subarray( |
| 20 | arr: Sequence[float], low: int, high: int |
| 21 | ) -> tuple[int | None, int | None, float]: |
| 22 | """ |
| 23 | Solves the maximum subarray problem using divide and conquer. |
| 24 | :param arr: the given array of numbers |
| 25 | :param low: the start index |
| 26 | :param high: the end index |
| 27 | :return: the start index of the maximum subarray, the end index of the |
| 28 | maximum subarray, and the maximum subarray sum |
| 29 | |
| 30 | >>> nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] |
| 31 | >>> max_subarray(nums, 0, len(nums) - 1) |
| 32 | (3, 6, 6) |
| 33 | >>> nums = [2, 8, 9] |
| 34 | >>> max_subarray(nums, 0, len(nums) - 1) |
| 35 | (0, 2, 19) |
| 36 | >>> nums = [0, 0] |
| 37 | >>> max_subarray(nums, 0, len(nums) - 1) |
| 38 | (0, 0, 0) |
| 39 | >>> nums = [-1.0, 0.0, 1.0] |
| 40 | >>> max_subarray(nums, 0, len(nums) - 1) |
| 41 | (2, 2, 1.0) |
| 42 | >>> nums = [-2, -3, -1, -4, -6] |
| 43 | >>> max_subarray(nums, 0, len(nums) - 1) |
| 44 | (2, 2, -1) |
| 45 | >>> max_subarray([], 0, 0) |
| 46 | (None, None, 0) |
| 47 | """ |
| 48 | if not arr: |
| 49 | return None, None, 0 |
| 50 | if low == high: |
| 51 | return low, high, arr[low] |
| 52 | |
| 53 | mid = (low + high) // 2 |
| 54 | left_low, left_high, left_sum = max_subarray(arr, low, mid) |
| 55 | right_low, right_high, right_sum = max_subarray(arr, mid + 1, high) |
| 56 | cross_left, cross_right, cross_sum = max_cross_sum(arr, low, mid, high) |
| 57 | if left_sum >= right_sum and left_sum >= cross_sum: |
| 58 | return left_low, left_high, left_sum |
| 59 | elif right_sum >= left_sum and right_sum >= cross_sum: |
| 60 | return right_low, right_high, right_sum |
| 61 | return cross_left, cross_right, cross_sum |
| 62 | |
| 63 | |
| 64 | def max_cross_sum( |
no test coverage detected