FYI, the answer to the EDIT:first tech interview is a rather clever dynamic programming solution. The thing to be careful of is that you can actually get two di

FYI, the answer to the EDIT:first tech interview is a rather clever dynamic programming solution. The thing to be careful of is that you can actually get two different dyn prog solutions: one which is O(n^2) and one which is O(nlog n). Also, the use of "ascending" seems inaccurate. Based on his example it looks closer to "monotonically non-decreasing." FWIW, it seems like a good problem to me. Dynamic programming is essential to finding good algorithmic solutions to many fundamental CS problems so I would expect everyone to be able to use it. Edit: Thanks to kenjackson for correcting my numbering. The second problem doesn't look like it requires dyn prog to me.