Box(s)

Time Limit: 1.5 sec

 

The Problem

You have given N boxes. Each box have a value, the value of box can be positive or negative. You need to choose some consecutive boxes that the total chosen box value is maximum.

 

Example:

Suppose you have 6 boxes with value -8, 4, -2, 5, -7, and 2. 

 

 

You can choose Box No. 2, Box No. 3, and Box No. 4, when you choose the boxes then the total value of chosen boxes are 4-2+5=7.

But you cannot choose Box No. 2, Box No. 4, and Box No. 6 because the box number are not consecutive. You must need to choose consecutive boxes. You also can choose 1 box, choose box number 4, now the total value of box is 5.

 

You can did it many different ways, like that

1. Choose Box No. 1, Box No. 2 (-8+4=-4)

2. Choose Box No. 1, Box No. 2, Box No. 3 (-8+4-2=-6)

3. Choose Box No. 1, Box No. 2, Box No. 3, Box No. 4 (-8+4-2+5=-1)

4. Choose Box No. 4, Box No. 5, Box No. 6 (5-7+2=0)

5. Choose Box No. 2 (4=4)

6. And so on

In this example the maximum value chosen boxes are 7 (Box No. 2, Box No. 3, and Box No. 4).

 

Write a simple program that can be calculated the maximum value of chosen box or boxes.

 

The Input

The input set consists of a positive number N ≤ 10000, that gives the length of the box sequence, followed by N integers, each integer greater than -1000 and less than 1000, denoted the value of each box. The input is terminated with N = 0.

 

The Output

For each given input set, the output will print a line “Set X: Y”, here X is the set number and Y is the maximum value of chosen box or boxes.

 

Sample Input

6

-8 4 -2 5 -7 2

3

1 2 3

4

4 -5 3 2

0

 

Sample Output

Set 1: 7

Set 2: 6

Set 3: 5

 

 

 

 

Online Practice Contest 3 [School & College Level]

Problem Setter: Shahin ShamS