有 n 张卡片，正反面皆有数字，有正有负。今要求每张卡片都从正反面中选一个数字，令他们的积最大。

有 n 张卡片，正反面皆有数字，有正有负。今要求每张卡片都从正反面中选一个数字，令他们的积最大。

除了子集枚举（DFS），还可以怎么做？（复杂度最高 O(n log n)）

累乘，保留前k项乘积的最大值和最小值。时间复杂度为O(N)
示例代码：

#include<stdio.h>

int main()
{
    int n,i;
    double a,b,min,max,t[4];
    scanf("%d",&n);//输入卡片个数
    if(n-->0){//第一对数字作为max和min的初值
        scanf("%lf%lf",&a,&b);
        if(a>b){
            max=a;
            min=b;
        }else{
            max=b;
            min=a;
        }
    }
    while(n-->0){
    //每次循环输入两个数字
        scanf("%lf%lf",&a,&b);
        //求出四个乘积
        t[0]=max*a;
        t[1]=min*a;
        t[2]=max*b;
        t[3]=min*b;
        //将四个乘积中最大的赋给max，最小的赋给min
        max=min=t[0];
        for(i=1;i<4;i++){
            if(t[i]>max)max=t[i];
            if(t[i]<min)min=t[i];
        }
    }
    printf("%lf",max);
    return 0;
}

img