problem!problem!

Discuss everything related to IOI here. For more general or advanced topics use CS forum.

Moderators:Labib, bristy1588

sakib
Posts:20
Joined:Tue Dec 07, 2010 3:33 pm
problem!problem!

Unread post by sakib » Mon Dec 13, 2010 1:33 pm

This is a tiny,simple and nice problem of dynamic programming.

You are given n integers(remember it includes 0 and negative numbers.otherwise this problem would be a joke).you can start at any i-th number(1<=i<=n) and stop at any j-th number(i<=j<=n) and take the sum of all the numbers between i and j.calculate the maximum possible sum.
here n<=1000000. so you have to solve it in O(n) complexity.

suppose there are 7 numbers 9,-10,-3,5,-2,8,-7 then the ans will be 11.
[you start from the 4th number 5 then add -2 and then 8 and stop.here sum will be 11 which will be the maximum possible sum].

Corei13
Posts:153
Joined:Tue Dec 07, 2010 9:10 pm
Location:Chittagong

Re: problem!problem!

Unread post by Corei13 » Mon Dec 20, 2010 9:56 pm

Let the n numbers stored in an array a[n], then the algo will be:

max = a[0]
for ( i = 1 ; i < n ; i++)
max = ( a >= 0 ) ? ( a + max ) : ( ( a >= max ) ? a : max ) )
ধনঞ্জয় বিশ্বাস

Corei13
Posts:153
Joined:Tue Dec 07, 2010 9:10 pm
Location:Chittagong

Re: problem!problem!

Unread post by Corei13 » Sat Dec 25, 2010 2:31 pm

Err... Last time i mixed max and max1!

Correct algo:

max = max1 = a[0]
for ( i = 1 ; i < n ; i++){
max1 = ( max1 >= 0 ) ? ( a + max1 ) : a
max = (max >= max1)?:max:max1
}
ধনঞ্জয় বিশ্বাস

Post Reply