problem!problem!

[sakib]

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]

[Moon]

You are in charge now! You take decision.
Anyway I don't have knowledge about the difficulty level of programming problems. However, I think that IOI forum should be used strictly for problem solving and discussion related to IOI (like IMO forum). We can use CS forum for other topics.
BTW I think that if we don't get more IOI oriented people this forum won't be alive.
I sent a mail to bd ioi training, but that forum is also dead (sort of). Is there any other forum on programming in BD?

[sakib]

I saw in CS group that some young people are talking about programming with interest.That's why posted this problem.This is a tiny problem.Lets check their interest and hope for the best.

[Annihilator]

we can use two variable. One will store maximum sum we've seen so far. Other will store current sum.

We'll start at index 0(by default in C/C++). initially, we'll store the first value of the array as max_sum.Then we'd start iteration.
each iteration through array, we'll add a value, if our current sum get negative, we'll set the value of current sum to 0 again & continue our iteration.We'll also check if cur_sum gets bigger than max_sum.If so, then we'd update.

[ridowan007]

If you understand the above algo then you can try this problem

https://www.spoj.pl/problems/MAXSUMSQ/

[Annihilator]

It gave me much fun solving that problem from Spoj.Thank you.

I am trying to learn dynamic programming. I have heard that there is such book which consists of 100 dp problems and their solutions.But the source couldn't mention me the name of that book. Could anyone name me that book please ?

Or, can anybody tell me how can I start learning dp ?

[sakib]

If you understand the above problem you must go for this-

http://acm.timus.ru/problem.aspx?space=1&num=1146