The Enchanted Forest Quest

Problem

Welcome, young wizard, to the Enchanted Forest, a place brimming with magical energy and ancient wisdom. Your task is to traverse a line of mystical trees, each radiating its own energy value, which can be positive, negative, or zero. The challenge lies in identifying the contiguous sequence of trees that yields the maximum possible energy. To achieve this, you'll wield the 'prefix sum' spell, a powerful algorithmic tool that will guide you in your quest. Step-by-step, you'll calculate cumulative energy values, uncovering the path that optimizes your energy collection. For example, given a line of trees with energy values [3, -2, 5, -1], the optimal path is the contiguous sequence [3, -2, 5] with a total energy of 6. Consider edge cases, such as all negative values or zeros, and remember that the sequence can be as short as a single tree.

Hints

Consider using the prefix sum technique to efficiently compute the maximum energy. Think about how to handle subarrays with negative sums and how they might affect your total. A sliding window approach might help streamline your calculations. Don't forget to consider edge cases like sequences with all negative or zero values. Focus on optimizing your solution to handle large numbers of trees efficiently.

Input format

The input consists of multiple lines. The first line contains an integer n (1 <= n <= 1000), the number of trees. The second line contains n integers, e[i] (-1000 <= e[i] <= 1000), representing the energy of each tree.

Output format

Output a single integer, the maximum possible energy that can be gathered from any contiguous sub-array of trees.

Constraints

1 <= n <= 1000; -1000 <= e[i] <= 1000

Sample input

5
3 -1 2 5 -2

Problem

Input format

Output format

Constraints

Sample input

Sample output