






'''simple docstring'''
import logging
import math
from functools import partial
from typing import Any, Callable, Dict, Iterable, List, Optional, Sequence, Tuple, Union

import torch

from .tensor_utils import tensor_tree_map, tree_map





def        _a(     UpperCamelCase__ :  Dict							):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__   : List[Any]													=[]
      if isinstance(__UpperCAmelCase,		__UpperCAmelCase							):
            for v in tree.values():
                  shapes.extend(_fetch_dims(__UpperCAmelCase							)							)
      elif isinstance(__UpperCAmelCase,		(list, tuple)							):
            for t in tree:
                  shapes.extend(_fetch_dims(__UpperCAmelCase							)							)
      elif isinstance(__UpperCAmelCase,		torch.Tensor							):
            shapes.append(tree.shape							)
      else:
            raise ValueError('''Not supported'''							)

      return shapes





@torch.jit.ignore
def        _a(     UpperCamelCase__ :  Optional[int],		UpperCamelCase__ :  Optional[Any]							):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__   : Any													=[]
      for d in reversed(__UpperCAmelCase							):
            idx.append(flat_idx % d							)
            SCREAMING_SNAKE_CASE__   : List[Any]													=flat_idx // d

      return tuple(reversed(__UpperCAmelCase							)							)





@torch.jit.ignore
def        _a(     UpperCamelCase__ :  Optional[int],		UpperCamelCase__ :  Any,		UpperCamelCase__ :  Optional[int],		UpperCamelCase__ :  List[Any] = None,		UpperCamelCase__ :  Union[str, Any] = None,		):




      '''simple docstring'''






      def reduce_edge_list(UpperCamelCase__ :  Tuple							) -> None:
            SCREAMING_SNAKE_CASE__   : str													=True
            for i in range(len(__UpperCAmelCase							)							):
                  SCREAMING_SNAKE_CASE__   : Optional[int]													=-1 * (i + 1)
                  l[reversed_idx] &= tally
                  SCREAMING_SNAKE_CASE__   : List[Any]													=l[reversed_idx]

      if start_edges is None:
            SCREAMING_SNAKE_CASE__   : Any													=[s == 0 for s in start]
            reduce_edge_list(__UpperCAmelCase							)
      if end_edges is None:
            SCREAMING_SNAKE_CASE__   : List[str]													=[e == (d - 1) for e, d in zip(__UpperCAmelCase,		__UpperCAmelCase							)]
            reduce_edge_list(__UpperCAmelCase							)

      # Base cases. Either start/end are empty and we're done, or the final,
      # one-dimensional tensor can be simply sliced
      if len(__UpperCAmelCase							) == 0:
            return [()]
      elif len(__UpperCAmelCase							) == 1:
            return [(slice(start[0],		end[0] + 1							),)]

      SCREAMING_SNAKE_CASE__   : List[Tuple[slice, ...]]													=[]
      SCREAMING_SNAKE_CASE__   : List[slice]													=[]

      # Dimensions common to start and end can be selected directly
      for s, e in zip(__UpperCAmelCase,		__UpperCAmelCase							):
            if s == e:
                  path_list.append(slice(__UpperCAmelCase,		s + 1							)							)
            else:
                  break

      SCREAMING_SNAKE_CASE__   : Tuple[slice, ...]													=tuple(__UpperCAmelCase							)
      SCREAMING_SNAKE_CASE__   : Optional[Any]													=len(__UpperCAmelCase							)

      # start == end, and we're done
      if divergence_idx == len(__UpperCAmelCase							):
            return [path]

      def upper() -> Tuple[Tuple[slice, ...], ...]:
            assert start_edges is not None
            assert end_edges is not None

            SCREAMING_SNAKE_CASE__   : Dict													=start[divergence_idx]
            return tuple(
                path + (slice(__UpperCAmelCase,		sdi + 1							),) + s
                for s in _get_minimal_slice_set(
                    start[divergence_idx + 1 :],		[d - 1 for d in dims[divergence_idx + 1 :]],		dims[divergence_idx + 1 :],		start_edges=start_edges[divergence_idx + 1 :],		end_edges=[True for _ in end_edges[divergence_idx + 1 :]],		)							)

      def lower() -> Tuple[Tuple[slice, ...], ...]:
            assert start_edges is not None
            assert end_edges is not None

            SCREAMING_SNAKE_CASE__   : Optional[int]													=end[divergence_idx]
            return tuple(
                path + (slice(__UpperCAmelCase,		edi + 1							),) + s
                for s in _get_minimal_slice_set(
                    [0 for _ in start[divergence_idx + 1 :]],		end[divergence_idx + 1 :],		dims[divergence_idx + 1 :],		start_edges=[True for _ in start_edges[divergence_idx + 1 :]],		end_edges=end_edges[divergence_idx + 1 :],		)							)

      # If both start and end are at the edges of the subtree rooted at
      # divergence_idx, we can just select the whole subtree at once
      if start_edges[divergence_idx] and end_edges[divergence_idx]:
            slices.append(path + (slice(start[divergence_idx],		end[divergence_idx] + 1							),)							)
      # If just start is at the edge, we can grab almost all of the subtree,
      # treating only the ragged bottom edge as an edge case
      elif start_edges[divergence_idx]:
            slices.append(path + (slice(start[divergence_idx],		end[divergence_idx]							),)							)
            slices.extend(lower()							)
      # Analogous to the previous case, but the top is ragged this time
      elif end_edges[divergence_idx]:
            slices.extend(upper()							)
            slices.append(path + (slice(start[divergence_idx] + 1,		end[divergence_idx] + 1							),)							)
      # If both sides of the range are ragged, we need to handle both sides
      # separately. If there's contiguous meat in between them, we can index it
      # in one big chunk
      else:
            slices.extend(upper()							)
            SCREAMING_SNAKE_CASE__   : str													=end[divergence_idx] - start[divergence_idx]
            if middle_ground > 1:
                  slices.append(path + (slice(start[divergence_idx] + 1,		end[divergence_idx]							),)							)
            slices.extend(lower()							)

      return slices





@torch.jit.ignore
def        _a(     UpperCamelCase__ :  List[str],		UpperCamelCase__ :  List[str],		UpperCamelCase__ :  List[str],		UpperCamelCase__ :  List[str]							):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__   : Dict													=t.shape[:no_batch_dims]
      SCREAMING_SNAKE_CASE__   : Dict													=list(_flat_idx_to_idx(__UpperCAmelCase,		__UpperCAmelCase							)							)
      # _get_minimal_slice_set is inclusive
      SCREAMING_SNAKE_CASE__   : Union[str, Any]													=list(_flat_idx_to_idx(flat_end - 1,		__UpperCAmelCase							)							)

      # Get an ordered list of slices to perform
      SCREAMING_SNAKE_CASE__   : Optional[Any]													=_get_minimal_slice_set(
          __UpperCAmelCase,		__UpperCAmelCase,		__UpperCAmelCase,		)

      SCREAMING_SNAKE_CASE__   : Tuple													=[t[s] for s in slices]

      return torch.cat([s.view((-1,) + t.shape[no_batch_dims:]							) for s in sliced_tensors]							)





def        _a(     UpperCamelCase__ :  Any,		UpperCamelCase__ :  Union[str, Any],		UpperCamelCase__ :  str,		UpperCamelCase__ :  Any,		UpperCamelCase__ :  Any = False,		UpperCamelCase__ :  Any = None,		UpperCamelCase__ :  Optional[int] = False,		):




      '''simple docstring'''






      if not (len(__UpperCAmelCase							) > 0):
            raise ValueError('''Must provide at least one input'''							)

      SCREAMING_SNAKE_CASE__   : Union[str, Any]													=[shape[:no_batch_dims] for shape in _fetch_dims(__UpperCAmelCase							)]
      SCREAMING_SNAKE_CASE__   : List[str]													=tuple([max(__UpperCAmelCase							) for s in zip(*__UpperCAmelCase							)]							)

      def _prep_inputs(UpperCamelCase__ :  Any							) -> torch.Tensor:
            if not low_mem:
                  if not sum(t.shape[:no_batch_dims]							) == no_batch_dims:
                        SCREAMING_SNAKE_CASE__   : Optional[Any]													=t.expand(orig_batch_dims + t.shape[no_batch_dims:]							)
                  SCREAMING_SNAKE_CASE__   : Any													=t.reshape(-1,		*t.shape[no_batch_dims:]							)
            else:
                  SCREAMING_SNAKE_CASE__   : Union[str, Any]													=t.expand(orig_batch_dims + t.shape[no_batch_dims:]							)
            return t

      SCREAMING_SNAKE_CASE__   : Dict[str, Any]													=tensor_tree_map(_prep_inputs,		__UpperCAmelCase							)
      SCREAMING_SNAKE_CASE__   : List[Any]													=None
      if _out is not None:
            SCREAMING_SNAKE_CASE__   : List[str]													=tensor_tree_map(lambda UpperCamelCase__							: t.view([-1] + list(t.shape[no_batch_dims:]							)							),		_out							)

      SCREAMING_SNAKE_CASE__   : List[Any]													=1
      for d in orig_batch_dims:
            flat_batch_dim *= d

      SCREAMING_SNAKE_CASE__   : str													=flat_batch_dim // chunk_size + (flat_batch_dim % chunk_size != 0)

      def _select_chunk(UpperCamelCase__ :  Optional[Any]							) -> torch.Tensor:
            return t[i : i + chunk_size] if t.shape[0] != 1 else t

      SCREAMING_SNAKE_CASE__   : int													=0
      SCREAMING_SNAKE_CASE__   : Tuple													=prepped_outputs
      for _ in range(__UpperCAmelCase							):
            # Chunk the input
            if not low_mem:
                  SCREAMING_SNAKE_CASE__   : int													=_select_chunk
            else:
                  SCREAMING_SNAKE_CASE__   : List[str]													=partial(
                      _chunk_slice,		flat_start=__UpperCAmelCase,		flat_end=min(__UpperCAmelCase,		i + chunk_size							),		no_batch_dims=len(__UpperCAmelCase							),		)

            SCREAMING_SNAKE_CASE__   : Dict[str, Any]													=tensor_tree_map(__UpperCAmelCase,		__UpperCAmelCase							)

            # Run the layer on the chunk
            SCREAMING_SNAKE_CASE__   : Optional[int]													=layer(**__UpperCAmelCase							)

            # Allocate space for the output
            if out is None:
                  SCREAMING_SNAKE_CASE__   : List[Any]													=tensor_tree_map(lambda UpperCamelCase__							: t.new_zeros((flat_batch_dim,) + t.shape[1:]							),		__UpperCAmelCase							)

            # Put the chunk in its pre-allocated space
            if isinstance(__UpperCAmelCase,		__UpperCAmelCase							):

                  def assign(UpperCamelCase__ :  Any,		UpperCamelCase__ :  Dict							) -> None:
                        for k, v in da.items():
                              if isinstance(__UpperCAmelCase,		__UpperCAmelCase							):
                                    assign(__UpperCAmelCase,		da[k]							)
                              else:
                                    if _add_into_out:
                                          v[i : i + chunk_size] += da[k]
                                    else:
                                          SCREAMING_SNAKE_CASE__   : int													=da[k]

                  assign(__UpperCAmelCase,		__UpperCAmelCase							)
            elif isinstance(__UpperCAmelCase,		__UpperCAmelCase							):
                  for xa, xa in zip(__UpperCAmelCase,		__UpperCAmelCase							):
                        if _add_into_out:
                              xa[i : i + chunk_size] += xa
                        else:
                              SCREAMING_SNAKE_CASE__   : Union[str, Any]													=xa
            elif isinstance(__UpperCAmelCase,		torch.Tensor							):
                  if _add_into_out:
                        out[i : i + chunk_size] += output_chunk
                  else:
                        SCREAMING_SNAKE_CASE__   : Union[str, Any]													=output_chunk
            else:
                  raise ValueError('''Not supported'''							)

            i += chunk_size

      SCREAMING_SNAKE_CASE__   : Dict													=tensor_tree_map(lambda UpperCamelCase__							: t.view(orig_batch_dims + t.shape[1:]							),		__UpperCAmelCase							)

      return out







class    __SCREAMING_SNAKE_CASE					:




 def __init__(					self		:							Optional[int]    ,					__lowercase		:							List[Any] = 5_12    ,					)		->  str:
       SCREAMING_SNAKE_CASE__   : int													=max_chunk_size
       SCREAMING_SNAKE_CASE__   : Optional[int]													=None
       SCREAMING_SNAKE_CASE__   : Optional[tuple]													=None




 def    __magic_name__		(					self		:							Any    ,					__lowercase		:							Optional[Any]    ,					__lowercase		:							List[str]    ,					__lowercase		:							Optional[int]					)		->  int:
       logging.info('''Tuning chunk size...'''					)

       if min_chunk_size >= self.max_chunk_size:
             return min_chunk_size

       SCREAMING_SNAKE_CASE__   : List[int]													=[2**l for l in range(int(math.log(self.max_chunk_size    ,					2					)					) + 1					)]
       SCREAMING_SNAKE_CASE__   : Dict													=[c for c in candidates if c > min_chunk_size]
       SCREAMING_SNAKE_CASE__   : int													=[min_chunk_size] + candidates
       candidates[-1] += 4

       def test_chunk_size(__lowercase		:							Optional[Any]					) -> bool:
             try:
                   with torch.no_grad():
                         fn(*_UpperCAmelCase    ,					chunk_size=_UpperCAmelCase					)
                   return True
             except RuntimeError:
                   return False

       SCREAMING_SNAKE_CASE__   : Any													=0
       SCREAMING_SNAKE_CASE__   : Optional[Any]													=len(_UpperCAmelCase					) - 1
       while i > min_viable_chunk_size_index:
             SCREAMING_SNAKE_CASE__   : List[Any]													=test_chunk_size(candidates[i]					)
             if not viable:
                   SCREAMING_SNAKE_CASE__   : List[str]													=(min_viable_chunk_size_index + i) // 2
             else:
                   SCREAMING_SNAKE_CASE__   : int													=i
                   SCREAMING_SNAKE_CASE__   : List[str]													=(i + len(_UpperCAmelCase					) - 1) // 2

       return candidates[min_viable_chunk_size_index]




 def    __magic_name__		(					self		:							Tuple    ,					__lowercase		:							List[Any]    ,					__lowercase		:							Optional[Any]					)		->  Optional[Any]:
       SCREAMING_SNAKE_CASE__   : Dict													=True
       for aa, aa in zip(_UpperCAmelCase    ,					_UpperCAmelCase					):
             assert type(_UpperCAmelCase					) == type(_UpperCAmelCase					)
             if isinstance(_UpperCAmelCase    ,					(list, tuple)					):
                   consistent &= self._compare_arg_caches(_UpperCAmelCase    ,					_UpperCAmelCase					)
             elif isinstance(_UpperCAmelCase    ,					_UpperCAmelCase					):
                   SCREAMING_SNAKE_CASE__   : Any													=[v for _, v in sorted(aa.items()    ,					key=lambda __lowercase					: x[0]					)]
                   SCREAMING_SNAKE_CASE__   : Dict													=[v for _, v in sorted(aa.items()    ,					key=lambda __lowercase					: x[0]					)]
                   consistent &= self._compare_arg_caches(_UpperCAmelCase    ,					_UpperCAmelCase					)
             else:
                   consistent &= aa == aa

       return consistent




 def    __magic_name__		(					self		:							Dict    ,					__lowercase		:							Any    ,					__lowercase		:							Union[str, Any]    ,					__lowercase		:							Optional[int]    ,					)		->  Optional[int]:
       SCREAMING_SNAKE_CASE__   : Dict													=True
       SCREAMING_SNAKE_CASE__   : tuple													=tree_map(lambda __lowercase					: a.shape if isinstance(_UpperCAmelCase    ,					torch.Tensor					) else a    ,					_UpperCAmelCase    ,					_UpperCAmelCase					)
       if self.cached_arg_data is not None:
             # If args have changed shape/value, we need to re-tune
             assert len(self.cached_arg_data					) == len(_UpperCAmelCase					)
             SCREAMING_SNAKE_CASE__   : int													=self._compare_arg_caches(self.cached_arg_data    ,					_UpperCAmelCase					)
       else:
             # Otherwise, we can reuse the precomputed value
             SCREAMING_SNAKE_CASE__   : Union[str, Any]													=False

       if not consistent:
             SCREAMING_SNAKE_CASE__   : List[Any]													=self._determine_favorable_chunk_size(
                 _UpperCAmelCase    ,					_UpperCAmelCase    ,					_UpperCAmelCase    ,					)
             SCREAMING_SNAKE_CASE__   : Union[str, Any]													=arg_data

       assert self.cached_chunk_size is not None

       return self.cached_chunk_size
"""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) = }''')
