"""simple docstring"""




from __future__ import annotations

import time
from collections.abc import Sequence
from random import randint

from matplotlib import pyplot as plt







def 				_UpperCAmelCase		(							lowerCamelCase__      ,	lowerCamelCase__      ,	lowerCamelCase__  ):





		"""simple docstring"""




		if not arr:
				return None, None, 0
		if low == high:
				return low, high, arr[low]

		lowerCAmelCase__   = (low + high) // 2
		lowerCAmelCase__ ,       lowerCAmelCase__ ,       lowerCAmelCase__   = max_subarray(lowerCamelCase__      ,	lowerCamelCase__      ,	lowerCamelCase__  )
		lowerCAmelCase__ ,       lowerCAmelCase__ ,       lowerCAmelCase__   = max_subarray(lowerCamelCase__      ,	mid + 1      ,	lowerCamelCase__  )
		lowerCAmelCase__ ,       lowerCAmelCase__ ,       lowerCAmelCase__   = max_cross_sum(lowerCamelCase__      ,	lowerCamelCase__      ,	lowerCamelCase__      ,	lowerCamelCase__  )
		if left_sum >= right_sum and left_sum >= cross_sum:
				return left_low, left_high, left_sum
		elif right_sum >= left_sum and right_sum >= cross_sum:
				return right_low, right_high, right_sum
		return cross_left, cross_right, cross_sum







def 				_UpperCAmelCase		(							lowerCamelCase__      ,	lowerCamelCase__      ,	lowerCamelCase__      ,	lowerCamelCase__  ):





		"""simple docstring"""




		lowerCAmelCase__ ,       lowerCAmelCase__   = float("""-inf"""  ), -1
		lowerCAmelCase__ ,       lowerCAmelCase__   = float("""-inf"""  ), -1

		lowerCAmelCase__   = 0
		for i in range(lowerCamelCase__      ,	low - 1      ,	-1  ):
				summ += arr[i]
				if summ > left_sum:
						lowerCAmelCase__   = summ
						lowerCAmelCase__   = i

		lowerCAmelCase__   = 0
		for i in range(mid + 1      ,	high + 1  ):
				summ += arr[i]
				if summ > right_sum:
						lowerCAmelCase__   = summ
						lowerCAmelCase__   = i

		return max_left, max_right, (left_sum + right_sum)







def 				_UpperCAmelCase		(							lowerCamelCase__  ):





		"""simple docstring"""




		lowerCAmelCase__   = [randint(1      ,	lowerCamelCase__  ) for _ in range(lowerCamelCase__  )]
		lowerCAmelCase__   = time.time()
		max_subarray(lowerCamelCase__      ,	0      ,	input_size - 1  )
		lowerCAmelCase__   = time.time()
		return end - start







def 				_UpperCAmelCase		(							):





		"""simple docstring"""




		lowerCAmelCase__   = [10, 100, 1000, 1_0000, 5_0000, 10_0000, 20_0000, 30_0000, 40_0000, 50_0000]
		lowerCAmelCase__   = [time_max_subarray(lowerCamelCase__  ) for input_size in input_sizes]
		print("""No of Inputs\t\tTime Taken"""  )
		for input_size, runtime in zip(lowerCamelCase__      ,	lowerCamelCase__  ):
				print(lowerCamelCase__      ,	"""\t\t"""      ,	lowerCamelCase__  )
		plt.plot(lowerCamelCase__      ,	lowerCamelCase__  )
		plt.xlabel("""Number of Inputs"""  )
		plt.ylabel("""Time taken in seconds"""  )
		plt.show()


if __name__ == "__main__":
			from doctest import testmod

			testmod()





"""simple docstring"""




def 				_UpperCAmelCase		(							lowerCamelCase__      ,	lowerCamelCase__  ):





		"""simple docstring"""




		return abs(lowerCamelCase__  ) if a == 0 else greatest_common_divisor(b % a      ,	lowerCamelCase__  )







def 				_UpperCAmelCase		(							lowerCamelCase__      ,	lowerCamelCase__  ):





		"""simple docstring"""




		while y:  # --> when y=0 then loop will terminate and return x as final GCD.
				lowerCAmelCase__ ,       lowerCAmelCase__   = y, x % y
		return abs(lowerCamelCase__  )







def 				_UpperCAmelCase		(							):





		"""simple docstring"""




		try:
				lowerCAmelCase__   = input("""Enter two integers separated by comma (,): """  ).split(""","""  )
				lowerCAmelCase__   = int(nums[0]  )
				lowerCAmelCase__   = int(nums[1]  )
				print(
				    f"""greatest_common_divisor({num_a}, {num_a}) = """
				    f"""{greatest_common_divisor(lowerCamelCase__      ,	lowerCamelCase__  )}"""  )
				print(f"""By iterative gcd({num_a}, {num_a}) = {gcd_by_iterative(lowerCamelCase__      ,	lowerCamelCase__  )}"""  )
		except (IndexError, UnboundLocalError, ValueError):
				print("""Wrong input"""  )


if __name__ == "__main__":
			main()




