算法

贪心

首先，分成两块来考虑，最大乘积为正、最大乘积为负。

假设最大乘积为正，使用i，j双指针分别位于头尾，排序后针对数组中头2个元素和尾两个元素，选择乘积大的，不断向中间靠拢。

最后注意k的值，若k减到0，则输出，若k为1且当前j指针上的位置的值>=0，也输出。若k为1且当前j指针上的位置小于0，表明无论如何乘积都为负，则反其道行之求。

若根据k和a[j]表明最大乘积为负，则无法用上述做法求，我们需反向贪心球的结果。同样使用双指针i,j，将绝对值小的数加入乘积中。

C++ 代码

#include<iostream>
#include<algorithm>
#define ll long long
#define mod 1000000009
using namespace std;

const int maxn=1e5+5;
int n,k;
ll a[maxn];

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    ll res=1;
    sort(a,a+n);
    int i=0, j=n-1, t=k;
    while(k>1){
        if(a[i]*a[i+1]>a[j]*a[j-1]){
            res=(res*(a[i]*a[i+1]%mod))%mod;
            i+=2;k-=2;
        }
        else{
            res=res*a[j]%mod;
            j--;k--;
        }
    }
    if((k&&a[j]>=0)){
        res=res*a[j]%mod;
        cout<<res;
    }
    else if(k==0) cout<<res;
    else{
        res=1;
        j=0;
        while(j<n&&a[j]<0) j++;
        i=j-1;
        for(k=0;k<t;k++){
            if(j==n) res=res*a[i--]%mod;
            else{
                if(abs(a[i])<=abs(a[j])) res=res*a[i--]%mod;
                else res=res*a[j++]%mod;
            }
        }
        cout<<res;
    }
    return 0;
}