题目描述

难度分:$1400$

输入$n(1 \leq n \leq 100)$和长为$n$的数组$a(-100 \leq a[i] \leq 100)$。

你需要从$a$中选择若干个数（至少一个），最大化所选数字的乘积。

输出你选的数字。如果答案不唯一，输出任意一个。

输入样例$1$

5
1 2 -3 3 3

输出样例$1$

1 2 3 3

输入样例$2$

13
100 100 100 100 100 100 100 100 100 100 100 100 100

输出样例$2$

100 100 100 100 100 100 100 100 100 100 100 100 100

输入样例$3$

4
-2 -2 -2 -2

输出样例$3$

-2 -2 -2 -2

算法

贪心

将数组$a$中的正数存入$pos$数组，负数全部存入$neg$数组，并统计数组中$0$的数量：

1. 如果只有$0$，输出个$0$就行。
2. 如果没有正数，只有一个负数。那么在数组中有$0$的情况下输出$0$，没有$0$的情况下输出那个唯一的负数。
3. 否则就正数全选，选择绝对值最大的偶数个负数（可以负负得正）。

复杂度分析

时间复杂度

可能需要对负数数组排序，由于原始数组$a$中有可能全是负数，所以最差情况下时间复杂度也是$O(nlog_2n)$。预处理出正数数组$pos$、负数数组$neg$、统计$0$的数量时间复杂度都是$O(n)$，因此整个算法的时间复杂度就是$O(nlog_2n)$。

空间复杂度

以快排为基准，排序的空间复杂度为$O(log_2n)$。但是空间消耗的瓶颈在于$pos$数组和$neg$数组，在最差情况下它们加在一起的空间是$O(n)$级别的，因此算法整体的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
int n, a;

int main() {
    scanf("%d", &n);
    int zero = 0;
    vector<int> pos, neg;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a);
        if(a > 0) {
            pos.push_back(a);
        }else if(a < 0) {
            neg.push_back(a);
        }else {
            zero++;
        }
    }
    if(pos.empty() && neg.empty()) {
        puts("0");
    }else if(pos.empty() && neg.size() == 1) {
        if(zero == 0) {
            printf("%d\n", neg[0]);
        }else {
            puts("0");
        }
    }else {
        for(int x: pos) {
            printf("%d ", x);
        }
        sort(neg.begin(), neg.end(), [&](int x, int y) {
            return abs(x) > abs(y);
        });
        for(int i = 1; i < neg.size(); i += 2) {
            printf("%d %d ", neg[i - 1], neg[i]);
        }
        puts("");
    }
    return 0;
}