





from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

UpperCAmelCase_					:   Tuple 							=						TypeVar("""KEY""")
UpperCAmelCase_					:   Any 							=						TypeVar("""VAL""")





@dataclass(frozen=_snake_case     ,					slots=_snake_case  )
class      lowercase__    (							Generic[KEY, VAL]  ):
  __UpperCamelCase	     =  42
  __UpperCamelCase	     =  42





class      lowercase__    (							_Item  ):







  def __init__(	self						):
       super().__init__(snake_case_    ,						snake_case_						)







  def __bool__(	self						):
       return False





UpperCAmelCase_					:   List[Any] 							=						_DeletedItem()





class      lowercase__    (							MutableMapping[KEY, VAL]  ):







  def __init__(	self    ,						_lowercase = 8    ,						_lowercase = 0.75						):
       lowerCAmelCase_					:       Tuple    =		initial_block_size
       lowerCAmelCase_					:       list[_Item | None]    =		[None] * initial_block_size
       assert 0.0 < capacity_factor < 1.0
       lowerCAmelCase_					:       List[str]    =		capacity_factor
       lowerCAmelCase_					:       Optional[Any]    =		0







  def 	UpperCAmelCase__		(	self    ,						_lowercase						):
       return hash(snake_case_						) % len(self._buckets						)







  def 	UpperCAmelCase__		(	self    ,						_lowercase						):
       return (ind + 1) % len(self._buckets						)







  def 	UpperCAmelCase__		(	self    ,						_lowercase    ,						_lowercase    ,						_lowercase						):
       lowerCAmelCase_					:       int    =		self._buckets[ind]
       if not stored:
            lowerCAmelCase_					:       Optional[int]    =		_Item(snake_case_    ,						snake_case_						)
            self._len += 1
            return True
       elif stored.key == key:
            lowerCAmelCase_					:       Dict    =		_Item(snake_case_    ,						snake_case_						)
            return True
       else:
            return False







  def 	UpperCAmelCase__		(	self						):
       lowerCAmelCase_					:       int    =		len(self._buckets						) * self._capacity_factor
       return len(self						) >= int(snake_case_						)







  def 	UpperCAmelCase__		(	self						):
       if len(self._buckets						) <= self._initial_block_size:
            return False
       lowerCAmelCase_					:       Union[str, Any]    =		len(self._buckets						) * self._capacity_factor / 2
       return len(self						) < limit







  def 	UpperCAmelCase__		(	self    ,						_lowercase						):
       lowerCAmelCase_					:       Union[str, Any]    =		self._buckets
       lowerCAmelCase_					:       Optional[Any]    =		[None] * new_size
       lowerCAmelCase_					:       Any    =		0
       for item in old_buckets:
            if item:
                 self._add_item(item.key    ,						item.val						)







  def 	UpperCAmelCase__		(	self						):
       self._resize(len(self._buckets						) * 2						)







  def 	UpperCAmelCase__		(	self						):
       self._resize(len(self._buckets						) // 2						)







  def 	UpperCAmelCase__		(	self    ,						_lowercase						):
       lowerCAmelCase_					:       List[str]    =		self._get_bucket_index(snake_case_						)
       for _ in range(len(self._buckets						)						):
            yield ind
            lowerCAmelCase_					:       List[str]    =		self._get_next_ind(snake_case_						)







  def 	UpperCAmelCase__		(	self    ,						_lowercase    ,						_lowercase						):
       for ind in self._iterate_buckets(snake_case_						):
            if self._try_set(snake_case_    ,						snake_case_    ,						snake_case_						):
                 break







  def __setitem__(	self    ,						_lowercase    ,						_lowercase						):
       if self._is_full():
            self._size_up()

       self._add_item(snake_case_    ,						snake_case_						)







  def __delitem__(	self    ,						_lowercase						):
       for ind in self._iterate_buckets(snake_case_						):
            lowerCAmelCase_					:       Tuple    =		self._buckets[ind]
            if item is None:
                 raise KeyError(snake_case_						)
            if item is _deleted:
                 continue
            if item.key == key:
                 lowerCAmelCase_					:       Dict    =		_deleted
                 self._len -= 1
                 break
       if self._is_sparse():
            self._size_down()







  def __getitem__(	self    ,						_lowercase						):
       for ind in self._iterate_buckets(snake_case_						):
            lowerCAmelCase_					:       Any    =		self._buckets[ind]
            if item is None:
                 break
            if item is _deleted:
                 continue
            if item.key == key:
                 return item.val
       raise KeyError(snake_case_						)







  def __len__(	self						):
       return self._len







  def __iter__(	self						):
       yield from (item.key for item in self._buckets if item)







  def __repr__(	self						):
       lowerCAmelCase_					:       Optional[int]    =		" ,".join(
           F'{item.key}: {item.val}' for item in self._buckets if item						)
       return F'HashMap({val_string})'












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) = }""")
