It's not about memorizing the answer to algorithm puzzles. In fact - if a candidate seems to know a problem by heart, that interviewer's feedback will often be discarded. It's about putting the candidate in a position where they have to think through a problem critically and seeing what trade-offs they make, what constraints they assume, and how they communicate their intent.
I have recommended hires for candidates who don't find the canonical solution many times.
Yes, I have. Generally this was a case where the candidate had a good grasp on an approach to the question by the end of the interview but wasn’t able to write it due to time constraints.
I see interviews as a dialogue between me and the candidate where I give them hints in the right direction when required. Very few candidates require 0 hints.
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.
I ran into this case studying for interviews a while ago. The "maximum subarray problem"[1] is a common interview question, you are generally expected to be able to come up with the O(n) solution.
Well has a great passage about the origins of the problem and how multiple excellent algorithmists could not improve on a O(n^2) run time[2]:
> Grenander observed that the cubic time of Algorithm 1 was prohibitively slow, and derived Algorithm 2. In 1977 he described the problem to Michael Shamos of UNILOGIC, Ltd. (then of Carnegie-Mellon University) who overnight designed Algorithm 3. When Shamos showed me the problem shortly thereafter, we thought that it was probably the best possible; researchers had just shown that several similar problems require time proportional to N log N. A few days later Shamos described the problem and its history at a seminar attended by Jay Kadane (a statistician at Carnegie-Mellon University), who designed the linear-time Algorithm 4 within a minute.
The solution is elegant and seemingly "obvious" after looking at it, but good luck coming up with it yourself :)
[1]: http://cricca.disi.unitn.it/montresor/wp-content/uploads/201... [2]: https://en.wikipedia.org/wiki/Maximum_subarray_problem