【题解】乘积最大

贪心

1. 如果 k == n ，只需要给出所有元素的乘积并取模。
2. 如果 k < n ，需要考虑 k 为奇数还是偶数。如果 k 为偶数，那么结果必然为非负。如果 k 为奇数，则存在结果为负的情况。
3. 如果结果必然为负，那么结果的绝对值越小，结果越大。如果结果为非负数，那么结果的绝对值越大，结果越大。

特殊情况

1. k < n 时，什么情况下结果必然为负？当 k 为奇数且所有元素均为负数时，结果必然为负数。否则只要存在一个数非负，就可以先选择该非负数，然后选择 k - 1 个负数。偶数个负数的结果为正数。
2. 这时问题统一转化为：取出偶数个元素，并使得乘积最大（注意区分结果为正数和负数的情况）。

双指针

1. 将所有元素排序。
2. 用两个指针指向序列首尾两端，每次从首尾两端各取出两个数，比较两个数的大小，取更大的那一端的两个数。这里的更大要区分正数和负数，正数是乘积绝对值最大，负数是乘积绝对值最小。

贪心 + 双指针 261ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, mod = 1000000009;

int n, k;
int a[N];

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    sort(a, a + n);

    // 双指针，l 和 r 分别表示两端选择的位置。
    // sign 用于区分结果最终为负数的情况（k为奇数，且 a 数组全部为负）。
    int l = 0, r = n - 1, sign = 1;
    // // k 为奇数
    int res = 1;
    if (k % 2) 
    {
        res = a[r --];
        k --;
        if (res < 0) sign = -1;
    }

    while (k)
    {
        // 注意，x 和 y 的值可以超过 int 
        LL x = (LL)a[l] * a[l + 1], y = (LL)a[r] * a[r - 1];
        if (x * sign > y * sign) 
        {
            res = (LL)x % mod * res % mod;
            l += 2;
        }
        else 
        {
            res = (LL)y % mod * res % mod;
            r -= 2;
        }
        k -= 2;
    }

    cout << res;
    return 0;
}