Maximum Gold Collection

Garnet has discovered a mysterious forest filled with ancient treasures and magical puzzles. Each treasure chest in this forest contains a certain number of gold coins, but some chests have puzzles that might subtract from her total coins. Garnet must traverse the forest by opening chests in their given order without skipping any. Her goal is to maximize the number of coins collected by choosing the optimal contiguous sequence of chests.

The problem can be modeled using the well-known Kadane's algorithm. The recurrence is given by:

$$current\_sum = \max(a_i,\; current\_sum + a_i)$$
$$max\_sum = \max(max\_sum,\; current\_sum)$$
You are guaranteed that Garnet must collect coins from at least one chest. ## inputFormat The input is read from standard input (stdin) and consists of two lines. The first line contains an integer \(n\) representing the number of chests. The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\), where each \(a_i\) represents the coins (positive or negative) in the \(i^{th}\) chest. ## outputFormat Output a single integer to standard output (stdout) which is the maximum number of coins Garnet can collect by selecting a contiguous segment of chests.## sample

4
1 2 3 4

10

$$