Maximum Sum of Beads

You are given a sequence of beads, where each bead has an integer weight. Your task is to determine the maximum sum you can obtain from any contiguous subsequence of beads. In other words, you should find the maximum sum of a consecutive segment in the array of bead weights.

Note: The subsequence must contain at least one bead. It can consist of a single bead if that yields the maximum sum.

The solution can be formulated using the well-known Kadane's algorithm. Mathematically, if we denote the weight of the i-th bead by \(a_i\), then the problem is to compute:

[ \max_{1 \leq i \leq j \leq N} \sum_{k=i}^{j} a_k ]

where \(N\) is the number of beads.

inputFormat

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

1. The first line contains a single integer \(N\) (the number of beads).
2. The second line contains \(N\) space-separated integers representing the weights of the beads.

outputFormat

Output the maximum sum that can be obtained from any contiguous subsequence of the given beads. The answer should be printed to stdout as a single integer.

6
-1 2 3 -5 4 6

10