Maximum Spell Strength

You are given a list of integers representing the magic power of a sequence of wizards. Your task is to determine the maximum possible spell strength by selecting a contiguous sub-array. In other words, you need to find the maximum subarray sum.

Mathematically, given an array \(a_1, a_2, \dots, a_n\), compute the maximum value of \(\sum_{i=l}^{r} a_i\) for \(1 \leq l \leq r \leq n\).

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

inputFormat

The input is given via standard input (stdin) and consists of two lines:

1. The first line contains an integer \(n\), representing the number of elements in the array.
2. The second line contains \(n\) space-separated integers, representing the magical powers.

outputFormat

Output the maximum spell strength, which is the maximum sum of a contiguous subarray. The output should be printed to standard output (stdout).

9
-2 1 -3 4 -1 2 1 -5 4

6