



class SCREAMING_SNAKE_CASE__     :




    '''simple docstring'''






    def __init__(       self,		lowerCamelCase__,		lowerCamelCase__		):
        A :       Union[str, Any]          =   name
        A :       Optional[Any]          =   val






    def __str__(       self		):
        return f'''{self.__class__.__name__}({self.name}, {self.val})'''






    def __lt__(       self,		lowerCamelCase__		):
        return self.val < other.val






class SCREAMING_SNAKE_CASE__     :




    '''simple docstring'''






    def __init__(       self,		lowerCamelCase__		):
        A :       Optional[Any]          =   {}
        A :       str          =   {}
        A :       Tuple          =   self.build_heap(lowerCamelCase__		)






    def __getitem__(       self,		lowerCamelCase__		):
        return self.get_value(lowerCamelCase__		)






    def 			_lowerCAmelCase					(       self,		lowerCamelCase__		):
        return (idx - 1) // 2






    def 			_lowerCAmelCase					(       self,		lowerCamelCase__		):
        return idx * 2 + 1






    def 			_lowerCAmelCase					(       self,		lowerCamelCase__		):
        return idx * 2 + 2






    def 			_lowerCAmelCase					(       self,		lowerCamelCase__		):
        return self.heap_dict[key]






    def 			_lowerCAmelCase					(       self,		lowerCamelCase__		):
        A :       Union[str, Any]          =   len(lowerCamelCase__		) - 1
        A :       int          =   self.get_parent_idx(lowerCamelCase__		)

        for idx, i in enumerate(lowerCamelCase__		):
            A :       Dict          =   idx
            A :       Tuple          =   i.val

        for i in range(lowerCamelCase__,		-1,		-1		):
            self.sift_down(lowerCamelCase__,		lowerCamelCase__		)
        return array






    def 			_lowerCAmelCase					(       self,		lowerCamelCase__,		lowerCamelCase__		):
        while True:
            A :       List[Any]          =   self.get_left_child_idx(lowerCamelCase__		)  # noqa: E741
            A :       List[str]          =   self.get_right_child_idx(lowerCamelCase__		)

            A :       List[str]          =   idx
            if l < len(lowerCamelCase__		) and array[l] < array[idx]:
                A :       Optional[Any]          =   l
            if r < len(lowerCamelCase__		) and array[r] < array[smallest]:
                A :       Union[str, Any]          =   r

            if smallest != idx:
                A     ,							A :       List[Any]          =   array[smallest], array[idx]
                (
                    (
                    A       
                )     ,							(
                    A       
                )     ,							       
                ) :       Optional[Any]          =   (
                    self.idx_of_element[array[smallest]],
                    self.idx_of_element[array[idx]],
                )
                A :       Union[str, Any]          =   smallest
            else:
                break






    def 			_lowerCAmelCase					(       self,		lowerCamelCase__		):
        A :       List[Any]          =   self.get_parent_idx(lowerCamelCase__		)
        while p >= 0 and self.heap[p] > self.heap[idx]:
            A     ,							A :       Optional[Any]          =   self.heap[idx], self.heap[p]
            A     ,							A :       Optional[int]          =   (
                self.idx_of_element[self.heap[idx]],
                self.idx_of_element[self.heap[p]],
            )
            A :       Optional[int]          =   p
            A :       Dict          =   self.get_parent_idx(lowerCamelCase__		)






    def 			_lowerCAmelCase					(       self		):
        return self.heap[0]






    def 			_lowerCAmelCase					(       self		):
        A     ,							A :       Tuple          =   self.heap[-1], self.heap[0]
        A     ,							A :       str          =   (
            self.idx_of_element[self.heap[-1]],
            self.idx_of_element[self.heap[0]],
        )

        A :       Dict          =   self.heap.pop()
        del self.idx_of_element[x]
        self.sift_down(0,		self.heap		)
        return x






    def 			_lowerCAmelCase					(       self,		lowerCamelCase__		):
        self.heap.append(lowerCamelCase__		)
        A :       str          =   len(self.heap		) - 1
        A :       Tuple          =   node.val
        self.sift_up(len(self.heap		) - 1		)






    def 			_lowerCAmelCase					(       self		):
        return len(self.heap		) == 0






    def 			_lowerCAmelCase					(       self,		lowerCamelCase__,		lowerCamelCase__		):
        assert (
            self.heap[self.idx_of_element[node]].val > new_value
        ), "newValue must be less that current value"
        A :       List[Any]          =   new_value
        A :       Optional[int]          =   new_value
        self.sift_up(self.idx_of_element[node]		)


SCREAMING_SNAKE_CASE_:List[str]             =						Node("""R""", -1)
SCREAMING_SNAKE_CASE_:int             =						Node("""B""", 6)
SCREAMING_SNAKE_CASE_:List[Any]             =						Node("""A""", 3)
SCREAMING_SNAKE_CASE_:List[str]             =						Node("""X""", 1)
SCREAMING_SNAKE_CASE_:int             =						Node("""E""", 4)

# Use one of these two ways to generate Min-Heap

# Generating Min-Heap from array
SCREAMING_SNAKE_CASE_:Dict             =						MinHeap([r, b, a, x, e])

# Generating Min-Heap by Insert method
# myMinHeap.insert(a)
# myMinHeap.insert(b)
# myMinHeap.insert(x)
# myMinHeap.insert(r)
# myMinHeap.insert(e)

# Before
print("""Min Heap - before decrease key""")
for i in my_min_heap.heap:
     print(i)

print("""Min Heap - After decrease key of node [B -> -17]""")
my_min_heap.decrease_key(b, -17)

# After
for i in my_min_heap.heap:
     print(i)

if __name__ == "__main__":
     import doctest

     doctest.testmod()









'''simple docstring'''

from collections.abc import Sequence





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

    _SCREAMING_SNAKE_CASE									=			0 if allow_empty_subarrays else float("""-inf"""    )
    _SCREAMING_SNAKE_CASE									=			0.0
    for num in arr:
        _SCREAMING_SNAKE_CASE									=			max(0 if allow_empty_subarrays else num					,       curr_sum + num    )
        _SCREAMING_SNAKE_CASE									=			max(__lowerCamelCase					,       __lowerCamelCase    )

    return max_sum


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

      testmod()

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



