Hacker News new | past | comments | ask | show | jobs | submit login

In section III B (p.8) the paper states that “in 1982…Gries[24] devised another linear algorithm” for the maximum subarray problem. I remember that. Jon Bentley visited Cornell, and posed the problem to me and Gries together. We thought on it independently overnight and presented a linear solution to Bentley the next day. Gries had a simpler invariant, and I had simpler code (using min). I never knew he wrote the paper until now, and am not one of the several people he mentions in the Acknowledgement, although he does say “Bentley…challenged US with this problem”.



There are a lot of trivial papers to be written when a field is young. Someone has to write them even if the discovery wasn't hard to make.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: