Maximum Bond Strength

You are given a sequence of integers representing the bond strengths of hexagonal tiles. Your task is to compute the maximum bond strength of any contiguous subsequence. In other words, you need to find the maximum sum of a contiguous subarray.

This can be formally defined as finding $$\max_{1 \leq i \leq j \leq n}\;\sum_{k=i}^{j}a_k,$$ where \(a_k\) denotes the bond strength of the \(k^{th}\) tile.

For example, if the input sequence is [1, -3, 2, 1, -1], the maximum bond strength is 3 (which comes from the subarray [2, 1]). Similarly, for the sequence [-2, -3, 4, -1, -2, 1, 5, -3], the answer is 7.

inputFormat

The first line of input contains an integer n – the number of hexagonal tiles. The second line contains n space-separated integers, representing the bond strengths of the tiles.

outputFormat

Output a single integer which is the maximum bond strength of any contiguous subsequence.

5
1 2 3 4 5

15