Maximum Contiguous Subsequence Sum

You are given an integer n and an array of n integers. Your task is to find the maximum sum of any contiguous subsequence of the array. Note that by definition, the sum of the empty subsequence is 0, so the answer is always non-negative.

This problem can be solved efficiently using Kadane's algorithm. Essentially, you iterate over the array while keeping track of the current running sum. If the running sum becomes negative, you reset it to zero. The maximum encountered running sum is the answer.

Formula: Use the recurrence relation \[ current\_sum = \max(a_i, current\_sum + a_i) \quad \text{for } 1 \le i \le n, \] where \(a_i\) represents the elements of the array. The answer is \(\max(0, \max(current\_sum))\).

inputFormat

The first line of the input contains a single integer n (0 ≤ n ≤ 10⁵), representing the number of elements in the array.

The second line contains n space-separated integers, which are the elements of the array.

If n is 0, the second line will be empty.

outputFormat

Output a single integer, which is the maximum sum of any contiguous subarray within the given array. Remember, the answer must be at least 0.

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

6