Maximum Popularity Sum

You are given an integer n representing the number of participants and a sequence of n integers indicating the popularity scores of these participants. Your task is to compute the maximum possible sum of a contiguous subsequence. If all scores are negative, output should be 0.

This problem is a variant of the classical Kadane's Algorithm. The recurrence relation used is given by: $$max\_ending\_here = \max(0, max\_ending\_here + score)$$ and $$max\_so\_far = \max(max\_so\_far, max\_ending\_here).$$

inputFormat

The first line contains an integer n (the number of participants). The second line contains n space-separated integers representing the popularity scores.

outputFormat

Output a single integer: the maximum sum of a contiguous subarray. If all values are negative, print 0.

5
-1 2 -3 4 5

9