

'''simple docstring'''


def 	_a       (				__lowerCAmelCase		:      List[str]   ,							__lowerCAmelCase		:      List[str]   ,							__lowerCAmelCase		:      Tuple   ,							__lowerCAmelCase		:      Union[str, Any]     ):

		"""simple docstring"""

		global f  # a global dp table for knapsack
		if f[i][j] < 0:
				if j < wt[i - 1]:
						snake_case__						:       Dict       						=  mf_knapsack(i - 1   ,							__lowerCAmelCase   ,							__lowerCAmelCase   ,							__lowerCAmelCase     )
				else:
						snake_case__						:       Optional[Any]       						=  max(
						    mf_knapsack(i - 1   ,							__lowerCAmelCase   ,							__lowerCAmelCase   ,							__lowerCAmelCase     )   ,							mf_knapsack(i - 1   ,							__lowerCAmelCase   ,							__lowerCAmelCase   ,							j - wt[i - 1]     ) + val[i - 1]   ,							)
				snake_case__						:       Optional[Any]       						=  val
		return f[i][j]




def 	_a       (				__lowerCAmelCase		:      List[Any]   ,							__lowerCAmelCase		:      Optional[int]   ,							__lowerCAmelCase		:      Tuple   ,							__lowerCAmelCase		:      Any     ):

		"""simple docstring"""

		snake_case__						:       Optional[int]       						=  [[0] * (w + 1) for _ in range(n + 1     )]

		for i in range(1   ,							n + 1     ):
				for w_ in range(1   ,							w + 1     ):
						if wt[i - 1] <= w_:
								snake_case__						:       Optional[int]       						=  max(val[i - 1] + dp[i - 1][w_ - wt[i - 1]]   ,							dp[i - 1][w_]     )
						else:
								snake_case__						:       List[str]       						=  dp[i - 1][w_]

		return dp[n][w_], dp




def 	_a       (				__lowerCAmelCase		:      int   ,							__lowerCAmelCase		:      list   ,							__lowerCAmelCase		:      list     ):

		"""simple docstring"""

		if not (isinstance(__lowerCAmelCase   ,							(list, tuple)     ) and isinstance(__lowerCAmelCase   ,							(list, tuple)     )):
				raise ValueError(
				    '''Both the weights and values vectors must be either lists or tuples'''     )

		snake_case__						:       str       						=  len(__lowerCAmelCase     )
		if num_items != len(__lowerCAmelCase     ):
				snake_case__						:       Tuple       						=  (
				    '''The number of weights must be the same as the number of values.\n'''
				    F"""But got {num_items} weights and {len(__lowerCAmelCase     )} values"""
				)
				raise ValueError(__lowerCAmelCase     )
		for i in range(__lowerCAmelCase     ):
				if not isinstance(wt[i]   ,							__lowerCAmelCase     ):
						snake_case__						:       Any       						=  (
						    '''All weights must be integers but got weight of '''
						    F"""type {type(wt[i]     )} at index {i}"""
						)
						raise TypeError(__lowerCAmelCase     )

		snake_case__						,       snake_case__						:       str       						=  knapsack(__lowerCAmelCase   ,							__lowerCAmelCase   ,							__lowerCAmelCase   ,							__lowerCAmelCase     )
		snake_case__						:       set       						=  set()
		_construct_solution(__lowerCAmelCase   ,							__lowerCAmelCase   ,							__lowerCAmelCase   ,							__lowerCAmelCase   ,							__lowerCAmelCase     )

		return optimal_val, example_optional_set




def 	_a       (				__lowerCAmelCase		:      list   ,							__lowerCAmelCase		:      list   ,							__lowerCAmelCase		:      int   ,							__lowerCAmelCase		:      int   ,							__lowerCAmelCase		:      set     ):

		"""simple docstring"""

		if i > 0 and j > 0:
				if dp[i - 1][j] == dp[i][j]:
						_construct_solution(__lowerCAmelCase   ,							__lowerCAmelCase   ,							i - 1   ,							__lowerCAmelCase   ,							__lowerCAmelCase     )
				else:
						optimal_set.add(__lowerCAmelCase     )
						_construct_solution(__lowerCAmelCase   ,							__lowerCAmelCase   ,							i - 1   ,							j - wt[i - 1]   ,							__lowerCAmelCase     )


if __name__ == "__main__":
					lowerCAmelCase__						:       Any										=						[3, 2, 4, 4]
					lowerCAmelCase__						:       Optional[int]										=						[4, 3, 2, 3]
					lowerCAmelCase__						:       List[str]										=						4
					lowerCAmelCase__						:       Dict										=						6
					lowerCAmelCase__						:       Tuple										=						[[0] * (w + 1)] + [[0] + [-1] * (w + 1) for _ in range(n + 1)]
					lowerCAmelCase__						,			lowerCAmelCase__						:       Dict										=						knapsack(w, wt, val, n)
					print(optimal_solution)
					print(mf_knapsack(n, wt, val, w))  # switched the n and w

					# testing the dynamic programming problem with example
					# the optimal subset for the above example are items 3 and 4
					lowerCAmelCase__						,			lowerCAmelCase__						:       Optional[Any]										=						knapsack_with_example_solution(w, wt, val)
					assert optimal_solution == 8
					assert optimal_subset == {3, 4}
					print("""optimal_value = """, optimal_solution)
					print("""An optimal subset corresponding to the optimal value""", optimal_subset)






'''simple docstring'''


from collections.abc import Sequence




def 	_a       (				__lowerCAmelCase		:      Sequence[int] | None = None     ):

		"""simple docstring"""

		if nums is None or not nums:
				raise ValueError('''Input sequence should not be empty'''     )

		snake_case__						:       Optional[Any]       						=  nums[0]
		for i in range(1   ,							len(__lowerCAmelCase     )     ):
				snake_case__						:       Tuple       						=  nums[i]
				snake_case__						:       Optional[int]       						=  max(__lowerCAmelCase   ,							ans + num   ,							__lowerCAmelCase     )

		return ans


if __name__ == "__main__":
					import doctest

					doctest.testmod()

					# Try on a sample input from the user
					lowerCAmelCase__						:       str										=						int(input("""Enter number of elements : """).strip())
					lowerCAmelCase__						:       Dict										=						list(map(int, input("""\nEnter the numbers : """).strip().split()))[:n]
					print(max_subsequence_sum(array))



