To solve this problem, we need to determine the maximum number of elements we can select from a sequence such that their product is positive.
Approach
- Categorize Elements: First, we categorize the elements into three groups: positive numbers, negative numbers, and zeros.
- Key Observations:
- Positive numbers always contribute to a positive product, so we should include all of them.
- Negative numbers contribute to a positive product if their count is even. If the count of negative numbers is odd, we need to exclude one (the one with the smallest absolute value to maximize the number of elements selected).
- Zeros cannot be included since they make the product zero, which is not positive.
- Edge Cases:
- If all elements are zeros, the result is zero.
- If there are no positive numbers and only one negative number, the result is zero (since including the negative number gives a negative product).
Solution Code
n = int(input())
arr = list(map(int, input().split()))
pos = 0
neg = 0
zero = 0
for num in arr:
if num > 0:
pos += 1
elif num < 0:
neg += 1
else:
zero += 1
if pos == 0 and neg == 0:
print(0)
else:
possible_neg = neg if neg % 2 == 0 else (neg - 1 if neg > 1 else 0)
total = pos + possible_neg
print(total if total != 0 else 0)
Explanation
- Categorization: We count the number of positive, negative, and zero elements in the input array.
- Calculate Possible Negatives: For negative numbers, if their count is even, we can include all of them. If it's odd, we exclude one (unless there's only one negative number, in which case we exclude it entirely).
- Compute Result: The result is the sum of all positive numbers and the possible negative numbers. If this sum is zero (e.g., no positives and only one negative), the result is zero.
This approach efficiently computes the solution with a time complexity of O(n), where n is the number of elements in the array, as we only traverse the array once to categorize elements. The space complexity is O(1) since we use a fixed number of variables.


作者声明:本文包含人工智能生成内容。