分析

• 使用双指针，奇数个负数不会影响结果，毕竟每次加入时是按最大值考虑的。
• 当结果是负数，考虑比较时，取绝对值较小的，也即带上符号后较大的。

C++ 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long LL ;
const int N = 100010 , mod = 1000000009 ;
int a[N];


int main()
{
    int n , k ;
    scanf("%d%d",&n,&k);
    for(int i = 0 ; i < n ; i ++) scanf("%d",&a[i]);

    sort(a,a + n);

    LL res = 1 ; //乘积初始化
    int l = 0 , r = n - 1 ;//双指针初始化
    int sign = 1 ; // 符号初始化

    //k 是奇数是先选出最大的数, k-- 就是偶数,两边再同时取对,转化成相同的双指针做法
    if(k&1)
    {
        res =  a[r]; // 取出最大的一个数
        r -- ; 
        k -- ; //个数减1
        if(res < 0) sign = -1;  // 如果最大值都是负数,就证明全是负数,那么符号要发生改变
    }

    // 双指针做法，选择更大的一对,和归并排序思路相近
    while(k)
    {
        LL x = (LL)a[l] * a[l + 1] , y = (LL)a[r] * a[r - 1];//两边同时取对

        if(x * sign > y * sign)
        {
            res = x % mod * res % mod;            
            l += 2;                                 
        }
        else 
        {
            res = y % mod * res % mod; 
            r -= 2; 
        }
        k -= 2; 
    }
    printf("%lld",res);
    return 0;
}