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]
problem!problem!
Moderators:Labib, bristy1588
Re: problem!problem!
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?
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?
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin
Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.
Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.
Re: problem!problem!
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
- Posts:4
- Joined:Mon Dec 13, 2010 11:32 pm
Re: problem!problem!
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.
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.
The question of whether computers can think is like the question of whether submarines can swim. ~ Edsger W. Dijkstra
-
- Posts:11
- Joined:Tue Dec 14, 2010 1:09 pm
Re: problem!problem!
If you understand the above algo then you can try this problem
https://www.spoj.pl/problems/MAXSUMSQ/
https://www.spoj.pl/problems/MAXSUMSQ/
- Annihilator
- Posts:4
- Joined:Mon Dec 13, 2010 11:32 pm
Re: problem!problem!
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 ?
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 ?
The question of whether computers can think is like the question of whether submarines can swim. ~ Edsger W. Dijkstra
Re: problem!problem!
If you understand the above problem you must go for this-
http://acm.timus.ru/problem.aspx?space=1&num=1146
http://acm.timus.ru/problem.aspx?space=1&num=1146