Counteroffer: if you know that it's being asked in an interview, it's much easier to come up with a neat and elegant answer. The test-taker within me pattern-m

Counteroffer: if you know that it's being asked in an interview, it's much easier to come up with a neat and elegant answer. The test-taker within me pattern-matches this problem to "interview question with a single-pass linear-time constant-space algorithm". Single-pass constant-space algorithms are so heavily constrained that they're much easier to find. The big hurdle for the maximum subarray problem is knowing that a single-pass constant-space algorithm exists; finding it under those conditions is not that hard. The original inventors of the algorithms you mention had a much harder job than an interview candidate does: they did not know what optimum to aim for.