标题：乘积最大
给定N个整数A1, A2, … AN。请你从中选出K个数，使其乘积最大。
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以1000000009的余数。
注意，如果X<0， 我们定义X除以1000000009的余数是负(-X)除以1000000009的余数。 即：0-((0-x) % 1000000009)
【输入格式】 第一行包含两个整数N和K。 以下N行每行一个整数Ai。
对于40%的数据，1 <= K <= N <= 100 对于60%的数据，1 <= K <= 1000 对于100%的数据，1 <= K <= N <= 100000 -100000 <= Ai <= 100000
【输出格式】 一个整数，表示答案。
【输入样例】 5 3 -100000 -10000 2 100000 10000
【输出样例】 999100009
再例如： 【输入样例】 5 3 -100000 -100000 -2 -100000 -100000
【输出样例】 -999999829
思路
这一题要分情况讨论，分负数个数为偶数和奇数，还有全为偶数的情况，k为偶数和奇数的情况，发现其规律，进行求解。
代码
#include <stdio.h>
typedef long long LL
;
const int mod
= 1000000009;
int compare(const void *a
, const void *b
)
{
return (*(int*)a
- *(int*)b
);
}
int main()
{
int n
, k
;
int A
[100010];
scanf("%d %d", &n
, &k
);
int i
;
for (i
= 0; i
< n
; i
++) scanf("%d", &A
[i
]);
qsort(A
, n
, sizeof(int), compare
);
int sign
= 1;
int l
= 0, r
= n
- 1;
LL res
= 1;
if (k
% 2 == 1) {
res
= A
[r
];
r
--;
k
--;
if (res
< 0) sign
= -1;
}
while (k
) {
LL x
= (LL
)A
[l
] * A
[l
+ 1];
LL 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;
}
