problem!problem!
Posted: 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].
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].