Maximum Non-Contiguous Subarray Sum

You are given an array of integers, a, which may include both positive and negative numbers. Your task is to compute the sum of a non-contiguous subarray with the maximum possible sum.

If there is at least one positive number in the array, the answer is the sum of all positive numbers. Otherwise, if all numbers are negative, the answer is the maximum (i.e. the least negative) number.

Formally, if the array is \(a = [a_1, a_2, \dots, a_n]\), then the answer is given by:

[ S = \begin{cases} \displaystyle \sum_{\substack{i=1 \ a_i>0}}^{n} a_i, & \text{if } \max(a) > 0 \ \max(a), & \text{if } \max(a) \le 0 \end{cases} ]

Read the input from standard input and print the result to standard output.

inputFormat

The input is read from standard input and it consists of two lines:

• The first line contains a single integer \(n\) (the number of elements in the array).
• The second line contains \(n\) space-separated integers, where each integer represents an element of the array \(a_i\).

outputFormat

Output a single integer which is the maximum sum of a non-contiguous subarray as defined above.

1
5

5