问题描述
给定 N 个整数 A1,A2,…AN。
请你从中选出 K 个数，使其乘积最大。
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009 的余数。
注意，如果 X<0， 我们定义 XX 除以 1000000009 的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行一个整数 Ai。
输出格式
输出一个整数，表示答案。
数据范围
1≤K≤N≤105,
−105≤Ai≤105
输入样例1：
5 3 -100000 -10000 2 100000 10000
输出样例1：
999100009
输入样例2：
5 3 -100000 -100000 -2 -100000 -100000
输出样例2：
-999999829
思路
直接上结论，我们需要先对所有数字进行排序， 然后再进行判断：
所以我们可以用双指针算法，具体思路如下：
1.先对所有数进行排序。
2.如果 k 为奇数，则需要将其变为偶数的情况再进行操作，同时用 sign 记录最终结果是正数还是负数，上面有提到过如果 k 是奇数需要分情况讨论，当所有数都是负数时，结果一定为负；当至少有一个数为正时，结果一定为正。所以我们只需取数组的最后一个数，判断其是否为负数即可。
3.此时，就可以按照当 k<n 且 k 为偶数的情况进行操作，只不过要根据 sign 的正负来进行选取。
设置一个左指针和一个右指针分别指向数组开头和结尾，然后分别取两个数相乘进行比较，由于此时的 k 为偶数，不会出现正负数落单的情况。
如果 sign 为正数，则选取相乘结果更小的；如果 sign 为负数，则选取相乘结果更大的，因为结果一定为负，则需要使相乘的绝对值越小越好，这样负数的绝对值越小，结果就越大。
4.输出最终结果。
代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 100010, mod = 1000000009; int a[N]; int n, k; int main() { scanf("%d%d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); //对所有数进行排序 //双指针算法 int l = 0, r = n - 1, res = 1; int sign = 1; if (k % 2) //k为奇数则需要转化成偶数 { res = a[r--]; k--; 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) //sign为正数，选值更大的 { res = x % mod * res % mod; l += 2; } else //sign为负数，选值更小的 { res = y % mod * res % mod; r -= 2; } k -= 2; } //输出结果 printf("%d\n", res); return 0; }
