Maximum Subarray Sum Excluding Negative-Only Subarrays

You are given a sequence of ( n ) integers. Your task is to find the maximum subarray sum with a twist: if all the numbers in the array are negative, the answer should be ( 0 ). In other words, if there exists at least one non-negative number, you must compute the maximum sum of any contiguous subarray using the standard dynamic programming approach (Kadane's algorithm), otherwise return (0).

The recurrence used in Kadane's algorithm is given by: ( dp_i = \max(a_i, dp_{i-1} + a_i) ) for ( i \ge 1 ).

inputFormat

The first line contains a single integer ( n ) ((1 \le n \le 10^5)), representing the number of elements in the sequence. The second line contains ( n ) space-separated integers ( a_1, a_2, \dots, a_n ) ((-10^9 \le a_i \le 10^9)).

outputFormat

Output a single integer, the maximum subarray sum according to the rules described above. If all numbers are negative, output (0).## sample

8
-2 -3 4 -1 -2 1 5 -3

7