[oluckyman]

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”.

[Jensson]

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.