Maximum product (greedy)

sample input 1：

5 3
-100000
-10000
2
100000
10000

sample output 1：

999100009

sample input 2：

5 3
-100000
-100000
-2
-100000
-100000

sample output 2：

-999999829

analysis ： This is a greedy question , It needs to be discussed according to the situation , We need to store positive and negative numbers separately （0 Treat as positive ）, Case one , The number of the given number is the same as the number to be selected , Then it's OK to choose all directly , There is also a situation where all numbers are negative , This should also be discussed separately , Let's sort the negative numbers first , If the number of numbers to be selected is odd , Then the final result must be negative , Then let's start with the largest negative number , choose k Up to the number , Because the larger the negative number, the smaller the absolute value , If the number of numbers to be selected is even , Because the final result is a positive , Then let's start with the smallest negative number , Until you finish selecting .

Now let's focus on how to choose when there are positive numbers , First of all, if you don't select all the numbers （ That is, at least one number can be left blank ） And there are positive numbers , Then the final result must be a non negative number （ At best, we don't choose a positive number or a negative number , This depends on the positive and negative of our product ）, At this time, if the number of selected numbers k It's an odd number , Then there is at least one positive number in our final number , So in order to maximize the product , Let's choose the largest positive number first , If k If it is an even number, you don't need to do this step , The rest of us just need to choose an even number , We compare the product of two negative numbers with the largest absolute value and the product of two positive numbers in turn ,（ It should be noted that we must choose in pairs ）, Who will vote and who will , Until the election is over , This is the optimal solution , The specific code is more complex , Here is the code ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1e5+10,mod=1000000009;
typedef long long ll;
ll z[N],f[N];
int main()
{
	int n,k;
	int zcnt=0,fcnt=0;
	cin>>n>>k;
	ll t;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&t);
		if(t>=0) z[++zcnt]=t;// contain 0 
		else f[++fcnt]=t; 
	}
	sort(z+1,z+zcnt+1);
	sort(f+1,f+fcnt+1);
	ll ans=1;
	if(fcnt+zcnt==k)
	{
		for(int i=1;i<=fcnt;i++)
			ans=ans*z[i]%mod;
		for(int i=1;i<=zcnt;i++)
			ans=ans*z[i]%mod;
		if(fcnt&1&&ans) printf("-");
		printf("%lld",(ans+mod)%mod);
		return 0;
	}
	if(zcnt==0)// There are only negative numbers 
	{
		if(k&1)// The number of selected numbers is odd , Then choose the larger of the negative numbers  
		{
			printf("-");
			for(int i=fcnt;i>fcnt-k;i--)
				ans=ans*(-f[i])%mod;
		}
		else// The number of selected numbers is even , Then choose the smaller of the negative numbers 
		{
			for(int i=1;i<=k;i++)
				ans=ans*f[i]%mod;
		}
	}
	else// There are positive numbers  
	{
		if(k&1)// The number of selected numbers is odd , First, select the number with the largest median of a positive number , Then compare and select other numbers  
			ans=ans*z[zcnt--]%mod,k--;
		int i,j;
		for(i=1,j=zcnt;i<=fcnt&&j>0&&k;)
		{
			if(f[i]*f[i+1]>z[j]*z[j-1])// Choose two currently selectable minimum negative numbers  
			{
				ans=f[i]*f[i+1]%mod*ans%mod;
				i+=2;
				k-=2;
			}
			else// Choose two currently selectable maximum positive numbers  
			{
				ans=z[j]*z[j-1]%mod*ans%mod;
				j-=2;
				k-=2;
			}
		}
		while(i<=fcnt&&k)
		{
			ans=f[i]*f[i+1]%mod*ans%mod;
			i+=2;
			k-=2;
		}
		while(j>0&&k)
		{
			ans=z[j]*z[j-1]%mod*ans%mod;
			j-=2;
			k-=2;
		}
	}
	printf("%lld",(ans+mod)%mod);
	return 0;
}