n個の数のうちk個を取って積を最大にする(c++実現)

タイトル:
N個の整数A 1,A 2,...AN.その中からK個の数を選んで、その積を最大にしてください.最大の積を求めてください.積が整数範囲を超えている可能性があるので、積を1000000009で割った残高を出力するだけです.なお、X<0の場合、Xを1000000009で割った剰余は、負(-X)を1000000009で割った剰余であると定義する.すなわち、0−((0−x)%1000000009)【入力フォーマット】1行目には2つの整数NとKが含まれる.以下のN行毎に1つの整数Aiがある.40%のデータに対して、1<=K<=N<=100は60%のデータに対して、1<=K<=1000は100%のデータに対して、1<=K<=N<=100000-100000<=Ai<=100000【出力フォーマット】1つの整数が答えを表す.【入力サンプル】5 3-100000-100000 2 100000【出力サンプル】99910009さらに例:【入力サンプル】5 3-100000-100000-2-100000-100000【出力サンプル】-9999999829リソース約定:ピークメモリ消費量(仮想マシン含む)<256 M
CPU消費<1000 ms
考え方:
使用する貪欲な思想.まず配列を絶対値サイズで昇順に並べ替え、右側のk個数を見ます.もしこのk個の数の積が正数であれば、もちろん私たちが望んでいる結果です.しかし、負数であれば、前の数から絶対値が最大の正数を探して、k数の絶対値が最小の負数を置き換える方法を考えなければならない.
もちろん、前の数に正数がなければ、絶対値が最大の負数を探して、後のk数の最小正数を置き換えるしかありませんが、後に正数がない可能性もあります.この場合、配列全体に正数がないことを示します.すべての結果は、絶対値が最も小さいk個の負数を乗算する(すなわち、このとき一番左のk個の数)はずです.最も複雑な場合は、前の数に正と負があり、後のk個の数にも正と負があるので、比較する必要があります.前から正数を探して積の最大を置換するか、負の数を探して積の最大を置換するかを比較する必要があります.
コード:
前の数の絶対値が最大の正数、負数、後のk個の数の最小の正数、負数を記録する必要があります(存在しない可能性があります).

#include 
#include 
#include 
#include 

using namespace std;

int n, k;
long long ans = 1;
int l_neg = -1, l_pos = -1, r_neg = -1, r_pos = -1;
const int M = 1000000009;

bool cmp(int a, int b)
{
	return abs(a) < abs(b);
}

int calc(vector a)
{
	long long temp = 1;
	for(int i = n - k; i < n; i++)
		temp = (temp * a[i]) % M;
	return temp;
}

bool v_cmp(vector a, vector b)
{
	int sum1 = 0, sum2 = 0;
	for(int i = n - k; i < n; i++){
		sum1 += abs(a[i]);
		sum2 += abs(b[i]);
	}
	return sum1 > sum2;
}

int main() {
	cin >> n >> k;
	vector a(n, 0);
	for(int i = 0; i < n; i++)
		cin >> a[i];
	sort(a.begin(), a.end(), cmp);

	for(int i = n - k; i < n; i++){
		ans = (ans * a[i]) % M;
		if(r_pos == -1 && a[i] > 0) r_pos = i;
		if(r_neg == -1 && a[i] < 0) r_neg = i;
	}
	for(int i = n - k - 1; i >= 0; i--){
		if(l_pos == -1 && a[i] > 0) l_pos = i;
		if(l_neg == -1 && a[i] < 0) l_neg = i;
	}
	
	if(ans < 0 && n != k){
		if(r_pos == -1){
			if(l_pos == -1){
				ans = 1;
				for(int i = 0; i < k; i++)
					ans = (ans * a[i]) % M;
			}
			else {
				swap(a[l_pos], a[r_neg]);
				ans = calc(a);
			}
		}
		else {
			if(l_neg == -1){
				swap(a[l_pos], a[r_neg]);
				ans = calc(a);
			}
			else if(l_pos == -1){
				swap(a[l_neg], a[r_pos]);
				ans = calc(a);
			}
			else {
				vector c1 = a;
				vector c2 = a;
				swap(c1[l_neg], c1[r_pos]);
				swap(c2[l_pos], c2[r_neg]);
				ans = v_cmp(c1, c2) == true? calc(c1): calc(c2);
			}
		}
	}
	cout << ans << endl;
	return 0;
}