Maximum Subarray Beauty

You are given an array of integers. Your task is to find the maximum "beauty" (i.e. the maximum sum of a contiguous subarray). This is a classic problem that can be efficiently solved using Kadane's algorithm.

Formally, given an array \(a_1, a_2, \dots, a_n\), find the maximum value of \(\sum_{k=i}^{j}a_k\) for any \(1 \le i \le j \le n\).

inputFormat

The first line of input contains an integer \(n\) (the number of elements in the array). The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer, the maximum sum of any contiguous subarray.

5
1 -2 3 4 -1

7