search

pllk / cphb

Competitive Programmer's Handbook
2.94k stars 354 forks source link

Maximum subarray sum wrong initialization #58

Closed alessandro-bugatti closed 6 years ago

alessandro-bugatti commented 6 years ago

In the algorithms that solve the maximum subarray sum problem, the best variabile is initialized to 0, where it should be initialized to array[0], otherwise, for example when all the elements are negative, the solution will be 0, that is not correct. What do you think?

pllk commented 6 years ago

There are two interpretations: is an empty sum allowed or not? If it is, the answer is always at least 0, which is the current interpretation in the book. I prefer this interpretation, and it also makes the code simpler. Also: if an empty sum is not allowed, what is the answer for an empty array? Maybe -∞?

alessandro-bugatti commented 6 years ago

I got the point, and I agree with your point of view. Maybe could you add a footnote (or similar) about that hypothesis (empty sum is allowed)?