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 (NCK) 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.
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.
For each set of input print in
a single line the summation of the integers in the desired subsequence.
4 4 1 2 3 4 4 1 1 2 3 4 4 2 4 4 –4 –4 0 0 |
10 4 8 |
Problem setter: Md. Kamruzzaman, EPS
Special Thanks: Monirul Hasan, EPS