2013年7月23日 星期二

10747 - Maximum Subsequence

給定 N 個整數,每個整數絕對值不大於 10,000,從裡面挑出 K 個數字相乘越大越好,然而這裡要求找到在最大乘積的情況下,最大總和為多少?

例如:有四個整數 4, 4, -4, -4,要求挑 2 個整數出來,有兩種方式可以得到最大值,分別是 4, 4 跟 -4, -4,但其中 4, 4 總和最大,因此答案為 8。 
Input
輸入最多 60 筆測資。 

每組測資第一行會有兩個整數 N, K (1<=K<=N<=10000),接下來會有 N 個整數。

N = K = 0 結束程式。

Output

對於每組測資,輸出一行描述的總和值。

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