Maximum Total Brightness of Lanterns

You are given a sequence of lanterns, where each lantern has an integer brightness value. Your task is to determine the maximum total brightness of any contiguous segment of lanterns.

Mathematically, given a sequence \(a_1, a_2, \dots, a_n\), you need to find:

[ \max_{1 \leq i \leq j \leq n} \left( \sum_{k=i}^{j} a_k \right) ]

This problem is a classic example of the maximum subarray problem, and can be solved efficiently using Kadane's algorithm.

inputFormat

The first line of input contains a single integer \(n\) representing the number of lanterns.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) indicating the brightness values of the lanterns.

outputFormat

Output a single integer which is the maximum total brightness of any contiguous segment of lanterns.

5
1 -2 3 4 -1

7