10.标题：乘积最大
给定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
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
分析：要用贪心的思想考虑
先处理数据，将正数从大到小排列，将负数按绝对值大小，从大到小排序，
然后在所有数据中，取绝对值前K的数字相乘，
所得乘积若为正数，就是最大值，取模输出。
若乘积为负数，有两种情况：
1.所给的数字中有正数，这种情况下，乘积虽然为负数，但是还是有一些正数或者负数没有用到，
可以将乘积所乘的绝对值最小的负数换成剩余数字中的最大的正数，
或者将乘积所乘的最小的正数换成剩余数字中绝对值最大的负数，
将乘积变为正数，再比较取最大的，取模输出。
2.所给的数字中只有负数，这种情况下，乘积为负数是因为，K为奇数，奇数个负数相乘，还是负数。
这时，重新按数值大小，将数字排序，取前K个数字乘积。
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int z[100005];
int f[100005];
bool cmp(int a,int b){//按照绝对值大小排序
return abs(a)>abs(b);
}
bool cmp1(int a,int b){//按照数值大小排序
return a>b;
}
int main(){
int n,k;
cin>>n>>k;
int k1=k;
int t1=0,t2=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(a[i]>0)//将正数与负数分别放到两个数组中
z[t1++]=a[i];
if(a[i]<0)
f[t2++]=a[i];
}
sort(z,z+t1,cmp);//正数排序，从大到小
sort(f,f+t2,cmp);//负数按绝对值的大小，从大到小排序
long long ans=1;//代表总乘积
int i1=0,i2=0;
while(1){
if(k==0)//用k记数，挑选完就结束
break;
if(abs(z[i1])>abs(f[i2])){//如果正数的绝对值较大，选正数
ans*=z[i1];
i1++;//下标向后移一个。代表原来的已经选完了
k--;//记数
}
else{//如果负数的绝对值较大，选负数
ans*=f[i2];
i2++;//下标向后移一个。代表原来的已经选完了
k--;//记数
}
}
if(ans>0){//如果最后乘积大于0，输出对10^9+9取模的结果
printf("%lld\n",ans%1000000009);
}
if(ans<0&&t1!=0){//如果乘积小于0，代表数值中有正有负,乘积为负数，将一个负数换成一个正数的方法，让乘积变成正数
long long ans1=0;
if(i1<t1)//如果正数没有用完的话
ans1=(ans/f[i2-1])*z[i1];//新的乘积，将最小的一个负数除去，乘上可以选择的最大的正数
if(i2<t2)//如果负数没有用完的话
ans=(ans/z[i1-1])*f[i2];//新的乘积，将最小的一个负数除去，乘上可以选择的最大的负数
if(ans1>ans)
printf("%lld",ans1%1000000009);
else{
printf("%lld",ans%1000000009);
}
}
if(ans<0&&t1==0){//如果数字全部是负数，那一定是最大的负数相乘所得的乘积最大
sort(f,f+t2,cmp1);//按照数值大小排序
long long ans2=1;
for(int i=0;i<k1;i++){
ans2*=f[i];
}
printf("%lld",ans2%1000000009);
}
return 0;
}