






'''simple docstring'''
from __future__ import annotations

import time

a_ 		=       list[tuple[int, int]]

a_ 		=       [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

a_ 		=       [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right






class    __SCREAMING_SNAKE_CASE					:




 def __init__(					self		:							Tuple    ,					__lowercase		:							Any    ,					__lowercase		:							str    ,					__lowercase		:							Tuple    ,					__lowercase		:							Optional[Any]    ,					__lowercase		:							Tuple					)		->  List[Any]:
       SCREAMING_SNAKE_CASE__   : Union[str, Any]													=pos_x
       SCREAMING_SNAKE_CASE__   : Any													=pos_y
       SCREAMING_SNAKE_CASE__   : Union[str, Any]													=(pos_y, pos_x)
       SCREAMING_SNAKE_CASE__   : int													=goal_x
       SCREAMING_SNAKE_CASE__   : List[Any]													=goal_y
       SCREAMING_SNAKE_CASE__   : Optional[Any]													=parent






class    __SCREAMING_SNAKE_CASE					:




 def __init__(					self		:							List[Any]    ,					__lowercase		:							Dict    ,					__lowercase		:							Optional[int]					)		->  Any:
       SCREAMING_SNAKE_CASE__   : Dict													=Node(start[1]    ,					start[0]    ,					goal[1]    ,					goal[0]    ,					_UpperCAmelCase					)
       SCREAMING_SNAKE_CASE__   : Union[str, Any]													=Node(goal[1]    ,					goal[0]    ,					goal[1]    ,					goal[0]    ,					_UpperCAmelCase					)

       SCREAMING_SNAKE_CASE__   : int													=[self.start]
       SCREAMING_SNAKE_CASE__   : List[str]													=False




 def    __magic_name__		(					self		:							List[Any]					)		->  Union[str, Any]:
       while self.node_queue:
             SCREAMING_SNAKE_CASE__   : str													=self.node_queue.pop(0					)

             if current_node.pos == self.target.pos:
                   SCREAMING_SNAKE_CASE__   : Tuple													=True
                   return self.retrace_path(_UpperCAmelCase					)

             SCREAMING_SNAKE_CASE__   : Optional[Any]													=self.get_successors(_UpperCAmelCase					)

             for node in successors:
                   self.node_queue.append(_UpperCAmelCase					)

       if not self.reached:
             return [self.start.pos]
       return None




 def    __magic_name__		(					self		:							int    ,					__lowercase		:							Any					)		->  List[str]:
       SCREAMING_SNAKE_CASE__   : List[Any]													=[]
       for action in delta:
             SCREAMING_SNAKE_CASE__   : Union[str, Any]													=parent.pos_x + action[1]
             SCREAMING_SNAKE_CASE__   : Optional[int]													=parent.pos_y + action[0]
             if not (0 <= pos_x <= len(grid[0]					) - 1 and 0 <= pos_y <= len(_UpperCAmelCase					) - 1):
                   continue

             if grid[pos_y][pos_x] != 0:
                   continue

             successors.append(
                 Node(_UpperCAmelCase    ,					_UpperCAmelCase    ,					self.target.pos_y    ,					self.target.pos_x    ,					_UpperCAmelCase					)					)
       return successors




 def    __magic_name__		(					self		:							Any    ,					__lowercase		:							List[str]					)		->  List[str]:
       SCREAMING_SNAKE_CASE__   : List[str]													=node
       SCREAMING_SNAKE_CASE__   : int													=[]
       while current_node is not None:
             path.append((current_node.pos_y, current_node.pos_x)					)
             SCREAMING_SNAKE_CASE__   : Tuple													=current_node.parent
       path.reverse()
       return path






class    __SCREAMING_SNAKE_CASE					:




 def __init__(					self		:							Dict    ,					__lowercase		:							str    ,					__lowercase		:							Optional[int]					)		->  str:
       SCREAMING_SNAKE_CASE__   : Optional[Any]													=BreadthFirstSearch(_UpperCAmelCase    ,					_UpperCAmelCase					)
       SCREAMING_SNAKE_CASE__   : Any													=BreadthFirstSearch(_UpperCAmelCase    ,					_UpperCAmelCase					)
       SCREAMING_SNAKE_CASE__   : Optional[Any]													=False




 def    __magic_name__		(					self		:							List[Any]					)		->  Optional[int]:
       while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
             SCREAMING_SNAKE_CASE__   : List[str]													=self.fwd_bfs.node_queue.pop(0					)
             SCREAMING_SNAKE_CASE__   : int													=self.bwd_bfs.node_queue.pop(0					)

             if current_bwd_node.pos == current_fwd_node.pos:
                   SCREAMING_SNAKE_CASE__   : int													=True
                   return self.retrace_bidirectional_path(
                       _UpperCAmelCase    ,					_UpperCAmelCase					)

             SCREAMING_SNAKE_CASE__   : Optional[Any]													=current_bwd_node
             SCREAMING_SNAKE_CASE__   : int													=current_fwd_node

             SCREAMING_SNAKE_CASE__   : int													={
                 self.fwd_bfs: self.fwd_bfs.get_successors(_UpperCAmelCase					),
                 self.bwd_bfs: self.bwd_bfs.get_successors(_UpperCAmelCase					),
             }

             for bfs in [self.fwd_bfs, self.bwd_bfs]:
                   for node in successors[bfs]:
                         bfs.node_queue.append(_UpperCAmelCase					)

       if not self.reached:
             return [self.fwd_bfs.start.pos]
       return None




 def    __magic_name__		(					self		:							Tuple    ,					__lowercase		:							Dict    ,					__lowercase		:							int					)		->  str:
       SCREAMING_SNAKE_CASE__   : Optional[int]													=self.fwd_bfs.retrace_path(_UpperCAmelCase					)
       SCREAMING_SNAKE_CASE__   : Optional[Any]													=self.bwd_bfs.retrace_path(_UpperCAmelCase					)
       bwd_path.pop()
       bwd_path.reverse()
       SCREAMING_SNAKE_CASE__   : Dict													=fwd_path + bwd_path
       return path


if __name__ == "__main__":
  # all coordinates are given in format [y,x]
  import doctest

  doctest.testmod()
  a_ 		=       (0, 0)
  a_ 		=       (len(grid) - 1, len(grid[0]) - 1)
  for elem in grid:
    print(elem)

  a_ 		=       time.time()
  a_ 		=       BreadthFirstSearch(init, goal)
  a_ 		=       bfs.search()
  a_ 		=       time.time() - start_bfs_time

  print('Unidirectional BFS computation time : ', bfs_time)

  a_ 		=       time.time()
  a_ 		=       BidirectionalBreadthFirstSearch(init, goal)
  a_ 		=       bd_bfs.search()
  a_ 		=       time.time() - start_bd_bfs_time

  print('Bidirectional BFS computation time : ', bd_bfs_time)
"""simple docstring"""






from collections.abc import Sequence



def SCREAMING_SNAKE_CASE__			(   __UpperCAmelCase       ,    __UpperCAmelCase = False )  ->  float:
   if not arr:
      return 0

   lowercase__:   Any					=      0 if allow_empty_subarrays else float('''-inf''' )
   lowercase__:   Union[str, Any]					=      0.0
   for num in arr:
      lowercase__:   List[str]					=      max(0 if allow_empty_subarrays else num       ,    curr_sum + num )
      lowercase__:   int					=      max(__UpperCAmelCase       ,    __UpperCAmelCase )

   return max_sum


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

       testmod()

       __A			   = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
       print(f'''{max_subarray_sum(nums) = }''')
