





'''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_							(					__lowercase							:      Sequence[float]			,     __lowercase							:      int			,     __lowercase							:      int       )		->       tuple[int | None, int | None, float]:


     '''simple docstring'''



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

     _UpperCAmelCase     							=   (low + high) // 2
     _UpperCAmelCase							,  _UpperCAmelCase							,  _UpperCAmelCase     							=   max_subarray(__lowercase			,     __lowercase			,     __lowercase       )
     _UpperCAmelCase							,  _UpperCAmelCase							,  _UpperCAmelCase     							=   max_subarray(__lowercase			,     mid + 1			,     __lowercase       )
     _UpperCAmelCase							,  _UpperCAmelCase							,  _UpperCAmelCase     							=   max_cross_sum(__lowercase			,     __lowercase			,     __lowercase			,     __lowercase       )
     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_							(					__lowercase							:      Sequence[float]			,     __lowercase							:      int			,     __lowercase							:      int			,     __lowercase							:      int       )		->       tuple[int, int, float]:


     '''simple docstring'''



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

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

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

     return max_left, max_right, (left_sum + right_sum)
def 	UpperCAmelCase_							(					__lowercase							:      int       )		->       float:


     '''simple docstring'''



     _UpperCAmelCase     							=   [randint(1			,     __lowercase       ) for _ in range(__lowercase       )]
     _UpperCAmelCase     							=   time.time()
     max_subarray(__lowercase			,     0			,     input_size - 1       )
     _UpperCAmelCase     							=   time.time()
     return end - start
def 	UpperCAmelCase_							(					)		->       None:


     '''simple docstring'''



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


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

  testmod()











from math import factorial




def 		lowerCAmelCase_    (  __UpperCAmelCase:			int		,   __UpperCAmelCase:			int      )      ->	int:

    # If either of the conditions are true, the function is being asked
    # to calculate a factorial of a negative number, which is not possible
    if n < k or k < 0:
        raise ValueError('''Please enter positive integers for n and k where n >= k'''      )
    return factorial(__UpperCAmelCase      ) // (factorial(__UpperCAmelCase      ) * factorial(n - k      ))


if __name__ == "__main__":
  print(
      'The number of five-card hands possible from a standard',
      F'''fifty-two card deck is: {combinations(52, 5)}\n''',
  )

  print(
      'If a class of 40 students must be arranged into groups of',
      F'''4 for group projects, there are {combinations(40, 4)} ways''',
      'to arrange them.\n',
  )

  print(
      'If 10 teams are competing in a Formula One race, there',
      F'''are {combinations(10, 3)} ways that first, second and''',
      'third place can be awarded.',
  )

