Maximum Subsequence Sum

Given a sequence of N integers, your task is to find the maximum possible sum of a contiguous subsequence. A subsequence is a contiguous segment of the array. The solution should work for sequences containing positive numbers, negative numbers, or both. Note that if all numbers are negative, the answer is the maximum (i.e., the least negative) among them.

You can refer to the classic Kadane's algorithm for an efficient approach. In mathematical terms, if the sequence is \(a_1, a_2, \dots, a_N\), you are required to compute:

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

For example, given the sequence [1, 2, -3, 4, 5, -6], the maximum subsequence sum is 9, which is achieved by the subsequence [4, 5].

inputFormat

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

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

outputFormat

Output a single integer to standard output (stdout) representing the maximum sum of any contiguous subsequence.

6
1 2 -3 4 5 -6

9