## 10747 - Maximum Subsequence

Moderator: Board moderators

Shahriar Nirjon
New poster
Posts: 16
Joined: Tue Dec 03, 2002 9:44 pm

### 10747 - Maximum Subsequence

<^7,

I tried to solve the problem 10747 Maximum Subsequence by sorting the numbers by their abs value ( and then replace one of the top K numbers when odd number of negative numbers is in first K) but WA. I also took special care for N=K, all positive, all negative cases.

I need some special input/output. Or any alternate way to solve

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:
Your method is good, but there are couple of special cases to consider:

for example, in the input:
4 2
7 -9 -10 100

you have to switch 7 for -10, and not -9 for 100.

Also, in the input
4 3
0 0 -1 -1

It is better to take 0 0 -1, as opposed to 0 -1 -1.

Shahriar Nirjon
New poster
Posts: 16
Joined: Tue Dec 03, 2002 9:44 pm

### Uff

<^7,
Alhamdulillah ! it's AC. I dedicate my solution to Marian.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
Problem statement:
You have to pick such a subsequence, so that multiplication of all its integers is maximum.
So if the input is

Code: Select all

``````6 3
-5
-10
-2
-4
-8
-12
``````
The output should be

Code: Select all

``-11``
right? (choosing -2, -4 and -5)

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
My solution produces for the following input

Code: Select all

``````6 6
-1
-2
-5
2
4
7
6 4
0
0
-12
12
-4
8
5 4
10
-20
12
0
5
4 3
9
10
-7
-100
4 4
1
2
3
4
4 1
1
2
3
4
4 2
4
4
-4
-4
4 2
-1
-3
-5
-7
4 2
-3
-7
0
-12
5 3
6
7
0
-3
-5
3 3
-2
-3
-4
4 4
-1
-2
-3
-4
5 3
-1
-2
-3
-4
0
1 1
3
2 1
-5
-7
0 0``````
this output:

Code: Select all

``````5
4
27
-97
10
4
8
-12
-19
-1
-9
-10
-3
3
-5
``````
Is this output correct?

Thanks, Erik

Shahriar Nirjon
New poster
Posts: 16
Joined: Tue Dec 03, 2002 9:44 pm

### yes

<^7,
Is this output correct?
Yes, your outputs are correct. (similar to my AC)

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

### Re: yes

Shahriar Nirjon wrote:<^7,
Is this output correct?
Yes, your outputs are correct. (similar to my AC)
Hello, I used the same method as you describe,and passed all the input/output above. But still get Wrong Answer.
Could someone offer me some critical input/output? thx

Shahriar Nirjon
New poster
Posts: 16
Joined: Tue Dec 03, 2002 9:44 pm

### Changed solution

<^7,
Hi,
I changed my algorithm since I could not make out how to handle special cases with that algo. The previous one (sort by abs value) was replaced by another one (trying to take big positive numbers, then even number of negetive numbers, finally special checks etc)

for special test case, u may try to generate tests where you must take at least one zero.

hope it helps.

Xmansk
New poster
Posts: 2
Joined: Mon Nov 10, 2008 2:29 pm

### Re: 10747 - Maximum Subsequence

Why for input

Code: Select all

``````6 4
0
0
-12
12
-4
8
``````
the outupt is

Code: Select all

``4``
shouldn't it be 24?

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

### Re: 10747 - Maximum Subsequence

Hi,
I don't know why the following input have such a strange answer...

input

Code: Select all

``````8 1
1 -1 -1 0 1 -3 -1 -1
8 2
1 -1 -1 0 1 -3 -1 -1
8 3
1 -1 -1 0 1 -3 -1 -1
8 4
1 -1 -1 0 1 -3 -1 -1
8 5
1 -1 -1 0 1 -3 -1 -1
8 6
1 -1 -1 0 1 -3 -1 -1
8 7
1 -1 -1 0 1 -3 -1 -1
8 8
1 -1 -1 0 1 -3 -1 -1
0 0
``````
output

Code: Select all

``````-4
-4
-3
-2
-5
-4
-4
-5
``````
why the first test case's output is -4?

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

### Re: 10747 - Maximum Subsequence

suneast wrote:Hi,
I don't know why the following input have such a strange answer...

input

Code: Select all

``````8 1
1 -1 -1 0 1 -3 -1 -1
8 2
1 -1 -1 0 1 -3 -1 -1
8 3
1 -1 -1 0 1 -3 -1 -1
8 4
1 -1 -1 0 1 -3 -1 -1
8 5
1 -1 -1 0 1 -3 -1 -1
8 6
1 -1 -1 0 1 -3 -1 -1
8 7
1 -1 -1 0 1 -3 -1 -1
8 8
1 -1 -1 0 1 -3 -1 -1
0 0
``````
output

Code: Select all

``````-4
-4
-3
-2
-5
-4
-4
-5
``````
why the first test case's output is -4?
My AC program outputs:

Code: Select all

``````1
-4
-3
-2
-5
-4
-2
-5``````

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

### Re: 10747 - Maximum Subsequence

Thx annhy

I have solved it a few months ago...
my output above is generated by UVaToolKit, I think there maybe something wrong with Toolkit's solution

Keep posting!
Happy AC

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10747 - Maximum Subsequence

Input:

Code: Select all

``````16 4
10
-81
-99
-99
-2
80
-18
79
11
-45
44
11
70
94
-90
-87
18 3
-21
-25
18
48
-25
91
60
23
84
65
61
32
36
-80
1
-13
-79
100
7 3
78
28
8
21
-61
-73
-36
14 6
46
-60
20
-80
8
-33
-55
-1
77
68
-18
-9
-22
64
3 1
-35
14
-30
18 6
24
92
-42
82
-38
-53
-91
26
-54
-50
-79
-64
20
92
45
37
-63
94
6 6
-75
54
-67
90
80
-18
7 3
52
-82
24
-75
-91
33
-93
12 11
-84
47
77
-84
69
63
36
60
-43
-78
47
-50
2 2
-24
-12
20 11
-83
17
-81
-89
-82
-63
-15
-56
97
68
-49
-83
-2
-83
64
-26
-67
32
87
19
3 3
41
89
-6
6 5
20
-37
-25
-15
-70
92
17 16
-90
-9
-23
-46
-63
-56
-45
-46
42
-28
-82
66
-45
0
3
24
42
13 9
31
91
-61
21
-39
-48
97
46
-18
88
-100
-26
48
2 1
52
-21
12 10
33
-63
-72
1
53
-17
-99
-45
-94
43
-99
-80
10 6
-91
-5
-97
-39
-9
-1
44
-72
-1
68
10 4
-32
28
70
-88
-15
-48
100
13
54
53
6 4
-93
53
-53
60
24
-79
19 19
16
-45
95
57
4
-12
85
-97
-45
11
-56
23
90
-87
-15
-26
-35
-15
87
7 7
33
-27
95
-64
-29
4
60
11 1
-8
8
61
-64
-36
-35
-26
99
-82
29
10
14 11
-1
-25
-13
73
-10
72
9
-91
59
93
-18
53
-72
3
9 1
45
63
80
-48
24
-84
-34
89
-10
7 3
70
75
-32
71
-77
-7
-43
8 2
-72
-46
42
37
97
75
-10
75
8 2
12
73
-91
-58
75
33
-42
-59
18 18
-44
-23
-83
-70
-5
89
-47
38
96
99
-29
75
-98
63
11
50
-13
51
18 17
-53
87
-63
-93
-72
-89
40
-64
-98
-89
-16
-92
-62
2
89
-16
-60
-59
15 3
90
-58
-91
43
-95
21
-8
-58
-29
66
57
-31
52
44
-24
1 1
66
1 1
27
19 6
16
52
5
100
92
-3
-80
-74
-64
-37
-64
29
-82
7
-80
-40
28
87
68
15 4
11
-78
-32
-84
39
-17
-25
-35
33
92
81
-16
-54
30
-25
11 7
-48
30
64
-62
-42
32
45
-71
42
-28
-85
2 2
3
71
4 2
87
30
-96
-39
15 4
-98
26
22
-51
-94
97
42
7
-52
-79
-30
-64
-20
52
81
15 1
-97
-26
-98
-78
77
23
-87
-2
-41
-6
-48
21
-61
39
-27
16 1
-28
21
-93
-86
-73
-95
-65
-53
-58
-35
99
73
74
-8
76
98
6 5
25
67
12
-78
76
-95
13 13
95
13
20
9
24
92
-70
-19
56
-43
-64
42
5
14 7
-47
-99
31
45
27
28
39
-25
-48
-45
37
-76
-69
-8
6 3
-14
62
97
95
-65
89
4 2
44
-68
52
-15
16 13
-58
40
82
73
-65
-42
-50
74
33
-47
-71
-81
-23
-90
11
-24
16 14
88
-66
92
-78
-78
-85
38
16
-53
-61
52
34
-81
44
-76
51
13 12
-91
16
-68
-8
69
-89
12
-54
-79
-78
-28
-41
-81
17 11
61
-19
-35
76
-82
31
74
-93
-68
-43
-73
76
-19
28
-59
-10
-13
12 7
80
-24
-16
-59
-28
-44
-87
44
-35
83
-98
58
4 3
73
-31
-49
3
5 1
36
-51
-64
11
-19
11 9
71
-99
-90
-57
31
-14
28
72
59
34
35
20 19
18
-45
6
-40
38
-22
-21
40
81
-29
49
16
21
85
78
52
-2
-70
22
-1
10 7
-71
26
94
51
-66
27
-14
-13
-25
-97
13 1
-87
-71
-42
-7
19
-62
14
-33
5
85
-49
-68
36
4 1
-92
99
2
24
20 7
-33
29
63
94
-86
100
-82
68
41
99
32
20
-94
75
-61
-56
-12
-44
-1
-27
2 2
-92
-93
``````
AC output:

Code: Select all

``````-375
275
-56
115
14
190
64
-132
103
-36
-379
124
-55
-266
122
52
-473
-187
34
-59
35
72
99
121
89
216
172
148
160
-710
-96
66
27
-124
11
-115
74
-135
-14
77
99
-5
160
-339
281
96
-202
-213
-532
-100
-67
-7
36
141
270
-87
85
99
256
-185
``````
Check input and AC output for thousands of problems on uDebug!

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

### Re: 10747 - Maximum Subsequence

I got a lot of WAs on this problem because my program would fail on cases that product of all selected numbers became zero and I hadn't noticed that by excluding negative numbers we would reach a better sum.
This testcase my help other people making the same mistake:

Input:

Code: Select all

``````6 4   5 -2 -1 0 0 0
4 4   1 2 3 4
4 1   1 2 3 4
4 2   4 4 -4 -4
5 1   -2 -1 0 1 2
3 1   -2 -1 0
3 1   0 1 2
3 1   -3 -2 -1
5 2   -2 3 0 0 0
5 3   -2 3 0 0 0
3 2   -2 -2 0
5 3   -5 -5 0 0 0
5 3   5 5 0 0 0
5 3   -5 5 0 0 0
5 4   -1 -1 5 5 0
5 4   -1 -1 -1 5 0
6 4   -1 -1 -1 5 0 0
5 3   -5 -1 -2 -4 -3
4 3   0 0 -1 -1
6 3   -5 -10 -2 -4 -8 -12
4 2   100 -10 -9 7
4 3   -100 -100 -99 1
4 2   200 -100 -3 -4
4 2   200 -100 3 4
6 4   -12 12 8 -4 0 0
0 0
``````
AC Output:

Code: Select all

``````5
10
4
8
2
0
2
-1
3
3
-4
0
10
5
8
3
4
-6
-1
-11
107
-199
-104
204
4
``````

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

### Re: 10747 - Maximum Subsequence

Code: Select all

``````13 12
49
-23
2
15
2
18
0
30
14
11
-23
7
-48
0 0``````
What about this case, the output is 77 in uva toolkit, an AC program is 125, another AC program is 102, but this program's output is 0 for case 1 1 -41, my WA program is 102. I think my output is correct, two AC program is wrong. Do I misunderstand the problem's meaning?