


'''simple docstring'''


from __future__ import annotations

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

from matplotlib import pyplot as plt







def 			snake_case_   (  SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__     ):







				"""simple docstring"""





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

				_SCREAMING_SNAKE_CASE :       Optional[Any]     		=      (low + high) // 2
				_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       str     		=      max_subarray(SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__     )
				_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       str     		=      max_subarray(SCREAMING_SNAKE_CASE__							,      mid + 1							,      SCREAMING_SNAKE_CASE__     )
				_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       int     		=      max_cross_sum(SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__     )
				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 			snake_case_   (  SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__							,      SCREAMING_SNAKE_CASE__     ):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       Union[str, Any]     		=      float("""-inf"""     ), -1
				_SCREAMING_SNAKE_CASE		,       _SCREAMING_SNAKE_CASE :       Optional[int]     		=      float("""-inf"""     ), -1

				_SCREAMING_SNAKE_CASE :       int | float     		=      0
				for i in range(SCREAMING_SNAKE_CASE__							,      low - 1							,      -1     ):
								summ += arr[i]
								if summ > left_sum:
												_SCREAMING_SNAKE_CASE :       Tuple     		=      summ
												_SCREAMING_SNAKE_CASE :       int     		=      i

				_SCREAMING_SNAKE_CASE :       int     		=      0
				for i in range(mid + 1							,      high + 1     ):
								summ += arr[i]
								if summ > right_sum:
												_SCREAMING_SNAKE_CASE :       Dict     		=      summ
												_SCREAMING_SNAKE_CASE :       List[str]     		=      i

				return max_left, max_right, (left_sum + right_sum)







def 			snake_case_   (  SCREAMING_SNAKE_CASE__     ):







				"""simple docstring"""





				_SCREAMING_SNAKE_CASE :       List[Any]     		=      [randint(1							,      SCREAMING_SNAKE_CASE__     ) for _ in range(SCREAMING_SNAKE_CASE__     )]
				_SCREAMING_SNAKE_CASE :       Tuple     		=      time.time()
				max_subarray(SCREAMING_SNAKE_CASE__							,      0							,      input_size - 1     )
				_SCREAMING_SNAKE_CASE :       Tuple     		=      time.time()
				return end - start







def 			snake_case_   (  ):







				"""simple docstring"""





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


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

				testmod()








'''simple docstring'''


import os
import sys
from contextlib import contextmanager


# Windows only
if os.name == "nt":
				import ctypes
				import msvcrt  # noqa





				class     lowercase__  (						ctypes.Structure					):





											'''simple docstring'''


											A_							:      Optional[Any]      	=  [("""size""", ctypes.c_int), ("""visible""", ctypes.c_byte)]







def 			snake_case_   (  ):







				"""simple docstring"""





				if os.name == "nt":
								_SCREAMING_SNAKE_CASE :       Tuple     		=      CursorInfo()
								_SCREAMING_SNAKE_CASE :       Tuple     		=      ctypes.windll.kernelaa.GetStdHandle(-11     )
								ctypes.windll.kernelaa.GetConsoleCursorInfo(SCREAMING_SNAKE_CASE__							,      ctypes.byref(SCREAMING_SNAKE_CASE__     )     )
								_SCREAMING_SNAKE_CASE :       Optional[Any]     		=      False
								ctypes.windll.kernelaa.SetConsoleCursorInfo(SCREAMING_SNAKE_CASE__							,      ctypes.byref(SCREAMING_SNAKE_CASE__     )     )
				elif os.name == "posix":
								sys.stdout.write("""\033[?25l"""     )
								sys.stdout.flush()







def 			snake_case_   (  ):







				"""simple docstring"""





				if os.name == "nt":
								_SCREAMING_SNAKE_CASE :       int     		=      CursorInfo()
								_SCREAMING_SNAKE_CASE :       List[str]     		=      ctypes.windll.kernelaa.GetStdHandle(-11     )
								ctypes.windll.kernelaa.GetConsoleCursorInfo(SCREAMING_SNAKE_CASE__							,      ctypes.byref(SCREAMING_SNAKE_CASE__     )     )
								_SCREAMING_SNAKE_CASE :       Tuple     		=      True
								ctypes.windll.kernelaa.SetConsoleCursorInfo(SCREAMING_SNAKE_CASE__							,      ctypes.byref(SCREAMING_SNAKE_CASE__     )     )
				elif os.name == "posix":
								sys.stdout.write("""\033[?25h"""     )
								sys.stdout.flush()







@contextmanager
def 			snake_case_   (  ):







				"""simple docstring"""





				try:
								hide_cursor()
								yield
				finally:
								show_cursor()




