We are going to solve yet another DP problem using the strategies we discussed in the previous post. If you haven’t, I strongly recommend you read my introduction post here, so it is easy to follow the slang.
Problem Definition: LIS (DPV, chapter 6.2)
We are given an array of numbers. A subsequence is a subset of these numbers taken in order, they can be consecutive or non-consecutive. An increasing subsequence is where the numbers are getting strictly larger. Our goal here is to find…
