





from __future__ import annotations

import math






def 							_lowerCAmelCase (  _a   :					int					,   _a   :					int					,   _a   :					bool					,   _a   :					list[int]					,   _a   :					float			)	->			int:

     if depth < 0:
          raise ValueError("""Depth cannot be less than 0"""			)

     if len(_a			) == 0:
          raise ValueError("""Scores cannot be empty"""			)

     if depth == height:
          return scores[node_index]

     if is_max:
          return max(
              minimax(depth + 1					,   node_index * 2					,   _a					,   _a					,   _a			)					,   minimax(depth + 1					,   node_index * 2 + 1					,   _a					,   _a					,   _a			)					,   )

     return min(
         minimax(depth + 1					,   node_index * 2					,   _a					,   _a					,   _a			)					,   minimax(depth + 1					,   node_index * 2 + 1					,   _a					,   _a					,   _a			)					,   )






def 							_lowerCAmelCase (  )	->			None:
     lowerCAmelCase_					:       Optional[int]    =		[90, 23, 6, 33, 21, 65, 1_23, 3_44_23]
     lowerCAmelCase_					:       Optional[Any]    =		math.log(len(_a			)					,   2			)
     print("""Optimal value : """					,   end=""""""			)
     print(minimax(0					,   0					,   _a					,   _a					,   _a			)			)


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      main()












from collections.abc import Sequence






def 							_lowerCAmelCase (  _a   :					Sequence[float]					,   _a   :					bool = False			)	->			float:
     if not arr:
          return 0

     lowerCAmelCase_					:       List[str]    =		0 if allow_empty_subarrays else float("""-inf"""			)
     lowerCAmelCase_					:       List[Any]    =		0.0
     for num in arr:
          lowerCAmelCase_					:       int    =		max(0 if allow_empty_subarrays else num					,   curr_sum + num			)
          lowerCAmelCase_					:       List[str]    =		max(_a					,   _a			)

     return max_sum


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

      testmod()

      UpperCAmelCase_					:   int 							=						[-2, 1, -3, 4, -1, 2, 1, -5, 4]
      print(F"""{max_subarray_sum(nums) = }""")
