| 62 | |
| 63 | |
| 64 | def max_cross_sum( |
| 65 | arr: Sequence[float], low: int, mid: int, high: int |
| 66 | ) -> tuple[int, int, float]: |
| 67 | left_sum, max_left = float("-inf"), -1 |
| 68 | right_sum, max_right = float("-inf"), -1 |
| 69 | |
| 70 | summ: int | float = 0 |
| 71 | for i in range(mid, low - 1, -1): |
| 72 | summ += arr[i] |
| 73 | if summ > left_sum: |
| 74 | left_sum = summ |
| 75 | max_left = i |
| 76 | |
| 77 | summ = 0 |
| 78 | for i in range(mid + 1, high + 1): |
| 79 | summ += arr[i] |
| 80 | if summ > right_sum: |
| 81 | right_sum = summ |
| 82 | max_right = i |
| 83 | |
| 84 | return max_left, max_right, (left_sum + right_sum) |
| 85 | |
| 86 | |
| 87 | def time_max_subarray(input_size: int) -> float: |