How to Find the Longest Increasing Subsequence of an Array

I explained to one of my neighbors, who's not in the industry, job searching in software dev is like the nightmare where you forgot that you had a college final and you haven't studied.

I explained to my cousin who does Power engineering, "Imagine I fail you for inability to solve hard calculus problems from sem 1 of college on a whiteboard, even though you don't need any more than basics".

He said, "I'd never subject myself to such crap interviewers"

This is a dynamic programming problem; if anyone wants a resource, I'd recommend this book [1]. Longest Increasing Subsequence is on page 162.

[1] http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-...

Interesting to see this posted as I'm taking algorithms this semester and the homework due in 2 weeks has a LIS question.

I accidentally implemented the longest common subsequence that runs in linear space[1] and it actually worked as a drop in replacement for LIS, for my particular question.

[1] http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Dyn...

I would fail this so hard

I'm pretty sure if you use a sorted map you can do this in n log n time, still with just n space.

edit: https://www.jdoodle.com/a/pZv