Maximum Energy

You are given a sequence of n integers representing energy values. Your task is to find the maximum possible total energy that can be collected by selecting a contiguous non-empty subarray.

Formally, given a sequence \(A_1, A_2, \dots, A_n\), you need to compute:

\(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} A_k\)

If all numbers are negative, the answer is the maximum (i.e., least negative) number.

This problem can be efficiently solved using Kadane's algorithm.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) representing the number of energy values.
• The second line contains \(n\) space-separated integers indicating the energy values.

outputFormat

Output a single integer which is the maximum total energy obtainable from any contiguous subarray.

5
-1 2 3 -2 4

7