Problem H
Maximum Subsequence

Input: Standard Input

Output: Standard Output

Time Limit: 2 Second

You are given a sequence of N integers, each of which is not greater than 10,000 considering absolute value. There are (^NC_K) sub-sequences possible from this sequence. You have to pick such a subsequence, so that multiplication of all its integers is maximum.

For example, if the sequence is 4, 4, -4, -4 and you are asked to pick 2 integers. You have 2 ways, which will satisfy the criterion. One is to pick 4,4 and the other is to pick –4, -4.

In this case, you have to consider the sub sequence whose summation of all integers is maximum.

Input

The input file contains several sets of inputs. The description of each set is given below.

Each input set starts with 2 positive integers N, K (1<=K<=N<=10000). Next N non-empty lines contain N integers in total.

Input is terminated by a case where N=0 and K=0. This case should not be processed. There will be at most 60 test cases.

Output

For each set of input print in a single line the summation of the integers in the desired subsequence.

Sample Input Output for Sample Input

4 4

1

2

3

4

4 1

1

2

3

4

4 2

4

4

–4

–4

0 0

10

4

8

題意：給定n個數字，中選出k個數字，使得乘積最大，如果有乘積相同的，就要和最大的。

思路：貪心，按數字絕對值從大到小排，相同按正數排前面，從頭選k個數字，如果選到0，說明乘積始終為0，那麼只要選最大的k個就可以了，如果這些數字負數個數為偶數個，乘積>0是最優，如果為奇數個。則要考慮：去掉一個正數換後面最大的負數，去掉一個負數換後面最大的正數。兩種情況比較乘積和總和，不過要注意，如果換到的是0的話要特殊考慮，並且在比較乘積的時候，整個乘積是保存不下來的，注意對於一次替換。sum = sum / m* z。這樣只要保存下m和z就可以比較了，細節比較多，寫得有點搓。

代碼：

#include 
#include 
#include 
#include 
#define max(a,b) (a)>(b)?(a):(b)
#define INF 0x3f3f3f3f
using namespace std;

const int N = 10005;

int n, k, seq[N];
bool cmp(int a, int b) {
	if (abs(a) != abs(b))
		return abs(a) > abs(b);
	return a > b;
}

void init() {
	for (int i = 0; i < n; i++)
		scanf("%d", &seq[i]);
}

int solve() {
	int sum = 0, fn = 0;
	sort(seq, seq + n, cmp);
	for (int i = 0; i < k; i++) {
		sum += seq[i];
		if (seq[i] < 0) fn++;
	}
	if (fn % 2) {
		int sum1 = -INF, sum2 = -INF, m1, z1, m2, z2;
		for (int i = k - 1; i >= 0; i--) {
			if (sum1 != -INF && sum2 != -INF) break;
			if (seq[i] > 0 && sum1 == -INF) {
				for (int j = k; j < n; j++) {
					if (seq[j] < 0) {
						sum1 = sum - seq[i] + seq[j];
						m1 = abs(seq[i]); z1 = abs(seq[j]);
						break;
					}
				}
			}
			else if (seq[i] < 0 && sum2 == -INF) {
				for (int j = k; j < n; j++) {
					if (seq[j] >= 0) {
						sum2 = sum - seq[i] + seq[j];
						m2 = abs(seq[i]); z2 = abs(seq[j]);
						break;
					}
				}
			}
			else if (seq[i] == 0) {
				sort(seq, seq + n);
				sum = 0;
				for (int i = n - 1; i >= n - k; i--)
					sum += seq[i];
				return sum;
			}
		}
		if (z2 == 0 && sum1 == -INF) {
			sort(seq, seq + n);
			sum = 0; int flag = 0;
			for (int i = n - 1; i > n - k; i--) {
				if (seq[i] == 0) flag = 1;
				sum += seq[i];
			}
			if (flag)
				sum += seq[n - k];
			return sum;
		}
		if (sum1 == -INF && sum2 == -INF) {
			sum = 0; for (int i = n - 1; i >= n - k; i--)
				sum += seq[i];
			return sum;
		}
		else if (sum1 == -INF && sum2 != -INF) return sum2;
		else if (sum1 != -INF && sum2 == -INF) return sum1;
		if (z1 * m2 == z2 * m1) sum = max(sum1, sum2);
		else if (z1 * m2 > z2 * m1) sum = sum1;
		else sum = sum2;
		
	}
	else {
		if (seq[k - 1] == 0) {
			sort(seq, seq + n);
			sum = 0;
			for (int i = n - 1; i >= n - k; i--)
				sum += seq[i];
		}
	}
	return sum;
}

int main() {
	while (~scanf("%d%d", &n, &k) && n + k) {
		init();
		printf("%d\n", solve());
	}
	return 0;
}