Maximum Park Beauty

You are given the heights of n buildings arranged in a row. The beauty of a park is defined as the maximum possible sum of heights of a contiguous sequence of buildings. Formally, if the heights are denoted by \(a_1, a_2, \dots, a_n\), you need to compute

[ \max_{1 \le i \le j \le n} \sum_{k=i}^{j} a_k ]

Your task is to implement a program that reads the list of building heights from standard input and prints the maximum beauty (i.e. the maximum subarray sum) to standard output.

Note that if all the building heights are negative, the answer is the largest (i.e. least negative) value.

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains a single integer \(n\) \( (1 \le n \le 10^5) \) denoting the number of buildings.
• The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the heights of the buildings. The values can be positive, zero, or negative.

outputFormat

Output a single integer to stdout: the maximum beauty of the park (i.e. the maximum contiguous subarray sum).

1
5

5