思路:

$一、K = n$
$所有数全选$
$二、K < n$
$1.K为偶数时，结果必然非负$
$(1)若负数有偶数个:则一对一对选取负数可保证结果非负$
$(2)若负数有奇数个:一定可以选择当前最大的负数$
$(在所有负数中绝对值最小)，永远不选取它(\because K < n)$
$剩下的负数成对选取，可保证结果非负$
$2.K为奇数时:分情况讨论$
$(1)若所有数均为负数，则结果为负数$
$(2)若所有数均为负数，则至少存在一个非负数，$
$先选取非负数中的最大者，再转换成情况1一对一对选取$
$(问题变成选取K-1个数，K-1为偶数)$

图解:

代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010, mod = 1000000009;

int n, k;
int a[N];

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

    int res = 1;
    int l = 0, r = n - 1;   // 双指针 分别从首尾往中间靠
    int sign = 1;
    if (k & 1)  // k是奇数 先取当前最大值 将问题转换成偶数情况(k-1为偶数)
    {
        res = a[r -- ]; // 取最大值
        k -- ;
        if (res < 0) sign = -1; // 说明结果为负 对应k为奇数且全为负数的情况
    }
    while (k)
    {
        // 每次选带上符号相乘后乘积最大的两个数(因为结果为正时 要选取乘积最大(不考虑符号时) 结果为负时 要选取乘积最小(不考虑符号时))
        LL x = (LL)a[l] * a[l + 1], y = (LL)a[r - 1] * a[r];
        if (x * sign > y * sign)
        {
            res = x % mod * res % mod;
            l += 2;
        }
        else
        {
            res = y % mod * res % mod;
            r -= 2;
        }
        k -= 2; 
    }

    printf("%d\n", res);

    return 0;
}