Maximum Subarray Sum

You are given an integer \( n \) and an array of \( n \) integers representing the beauty factors of photos. Your task is to find the maximum sum of any contiguous subarray. This is a classic problem which can be efficiently solved using Kadane's algorithm.

Let the array be denoted as \( a_1, a_2, \ldots, a_n \). The goal is to maximize the sum \( S = a_i + a_{i+1} + \cdots + a_j \) for some \( 1 \le i \le j \le n \). In other words, find: \[ \max_{1 \le i \le j \le n}\left(\sum_{k=i}^{j} a_k\right) \]

If all numbers are negative, the answer is the maximum (least negative) number.

inputFormat

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

1. The first line contains an integer \( n \) denoting the number of photos.
2. The second line contains \( n \) space-separated integers representing the beauty factors of the photos.

outputFormat

Output the maximum sum of beauty factors of any contiguous subarray to stdout.

6
1 -2 3 4 -1 2

8