


from collections.abc import Sequence






def 					lowerCamelCase_   (	_a     ,       _a = False	):




		"""simple docstring"""






		if not arr:
				return 0

		lowerCAmelCase__       :      Tuple   					= 0 if allow_empty_subarrays else float('''-inf'''	)
		lowerCAmelCase__       :      Dict   					= 0.0
		for num in arr:
				lowerCAmelCase__       :      Any   					= max(0 if allow_empty_subarrays else num     ,       curr_sum + num	)
				lowerCAmelCase__       :      Optional[int]   					= max(_a     ,       _a	)

		return max_sum


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

		testmod()

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



# using dfs for finding eulerian path traversal






def 					lowerCamelCase_   (	_a     ,       _a     ,       _a     ,       _a=None	):




		"""simple docstring"""






		lowerCAmelCase__       :      Optional[Any]   					= (path or []) + [u]
		for v in graph[u]:
				if visited_edge[u][v] is False:
						lowerCAmelCase__					,     lowerCAmelCase__       :      List[Any]   					= True, True
						lowerCAmelCase__       :      Any   					= dfs(_a     ,       _a     ,       _a     ,       _a	)
		return path






def 					lowerCamelCase_   (	_a     ,       _a	):




		"""simple docstring"""






		lowerCAmelCase__       :      Union[str, Any]   					= 0
		lowerCAmelCase__       :      str   					= -1
		for i in range(_a	):
				if i not in graph.keys():
						continue
				if len(graph[i]	) % 2 == 1:
						odd_degree_nodes += 1
						lowerCAmelCase__       :      Tuple   					= i
		if odd_degree_nodes == 0:
				return 1, odd_node
		if odd_degree_nodes == 2:
				return 2, odd_node
		return 3, odd_node






def 					lowerCamelCase_   (	_a     ,       _a	):




		"""simple docstring"""






		lowerCAmelCase__       :      Optional[Any]   					= [[False for _ in range(max_node + 1	)] for _ in range(max_node + 1	)]
		lowerCAmelCase__					,     lowerCAmelCase__       :      Optional[int]   					= check_circuit_or_path(_a     ,       _a	)
		if check == 3:
				print('''graph is not Eulerian'''	)
				print('''no path'''	)
				return
		lowerCAmelCase__       :      Optional[int]   					= 1
		if check == 2:
				lowerCAmelCase__       :      Any   					= odd_node
				print('''graph has a Euler path'''	)
		if check == 1:
				print('''graph has a Euler cycle'''	)
		lowerCAmelCase__       :      Optional[int]   					= dfs(_a     ,       _a     ,       _a	)
		print(_a	)






def 					lowerCamelCase_   (	):




		"""simple docstring"""






		lowerCAmelCase__       :      List[str]   					= {1: [2, 3, 4], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [4]}
		lowerCAmelCase__       :      Tuple   					= {1: [2, 3, 4, 5], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [1, 4]}
		lowerCAmelCase__       :      str   					= {1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2], 4: [1, 2, 5], 5: [4]}
		lowerCAmelCase__       :      List[str]   					= {1: [2, 3], 2: [1, 3], 3: [1, 2]}
		lowerCAmelCase__       :      List[Any]   					= {
		    1: [],
		    2: []
		    # all degree is zero
		}
		lowerCAmelCase__       :      Optional[Any]   					= 10
		check_euler(_a     ,       _a	)
		check_euler(_a     ,       _a	)
		check_euler(_a     ,       _a	)
		check_euler(_a     ,       _a	)
		check_euler(_a     ,       _a	)


if __name__ == "__main__":
		main()




