Maximum Firework Sum

You are given an array of integers which can be interpreted as the intensity changes in a fireworks display. Your task is to find the maximum sum of a contiguous subarray. This is the classic maximum subarray problem that can be solved efficiently using Kadane's algorithm.

More formally, if the subarray from index i to j has elements \(a_i, a_{i+1}, \ldots, a_j\), its sum is given by \(\sum_{k=i}^{j} a_k\). You need to find the maximum such sum over all possible contiguous subarrays.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer \(n\) \((1 \le n \le 10^5)\), representing the number of elements in the array. The second line contains \(n\) space-separated integers, each representing an element of the array.

outputFormat

Output to standard output (stdout) a single integer: the maximum sum of any contiguous subarray of the given array.

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

6