给定 N 个整数 A1,A2,…AN

。

请你从中选出 K

个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009

的余数。

注意，如果 X<0
， 我们定义 X 除以 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
思路：枚举k和n的关系 如果相等，那自然要全取，如果k<n，当k是偶数的时候，答案一定大于零，证明：如果n中有奇数个负数，一定存在答案可以大于0，如果有偶数个负数，也一样。如果k为奇数，那就可以划分成k-1和1，如果最大值都小于0，那肯定小于0，最大值大于0，那么一定大于0.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const   int N=100010;
int a[N];
const  int mod=1000000009; int main()
{
   
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    cin>>a[i];
    int l=0,r=n-1;
    sort(a,a+n);
    int sign=1;
    long long res=1; if(k%2)
    {
   
        res=a[r--];
        if(res<0)
        sign=-1;
        k--;
    }
    while(k)
    {
   
        long long x=(ll)a[l]*a[l+1],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;
    }
    cout<<res<<endl;
    return 0;
}