Maximum Subsequence Sum

You are given a sequence of n integers. Your task is to find the maximum sum of any continuous subsequence from the given sequence.

The problem is a classic dynamic programming problem known as the Maximum Subarray Problem and can be solved using Kadane's algorithm. The algorithm works in O(n) time and is optimal for sequences of large size.

Mathematical Formulation:

Let \(a_1, a_2, \ldots, a_n\) be the sequence. You need to compute the maximum value of \(\sum_{i=l}^{r}a_i\) for \(1 \leq l \leq r \leq n\).

inputFormat

The first line contains an integer n (\(1 \leq n \leq 10^5\)), representing the number of elements in the sequence. The second line contains n space-separated integers \(a_1, a_2, \ldots, a_n\) where each \(a_i\) satisfies \(-10^4 \leq a_i \leq 10^4\).

outputFormat

Output a single integer which is the maximum sum of any continuous subsequence of the given sequence.

9
-2 1 -3 4 -1 2 1 -5 4

6