也就是说对于我们经过处理之后得到的这个dp数组当中的元素必然是递增的，所以，其中每一个元素所在的位置其实就代表这个元素对应的长度。比如上图当中2排在数组当中的第二位，那么就说明2这个数字对应的答案是2。
我们更新dp数组的过程主要做了两件事，第一件事是让dp数组当中的元素尽量多，我们每次都会把最大的数插入dp的末尾。另外一件事情就是让dp数组当中的每个位置的元素尽量小。这样才可以为只有插入尽可能多的元素做准备，如果前面的数就特别大，那后面就没办法传入其他数了。
比如上图当中的3和9的答案都是3，但是显然3比9更好，因为3能够达到答案3，说明出现在3右侧的只要大于3的数至少可以获得4的长度。我们既可以理解成3对应的答案是3，也可以理解成答案3对应的最小满足的数是3，而不是9。
由于dp数组当中的元素有序，我们可以使用二分法来找到对应更新的位置，从而可以保证我们可以在logN的时间内找到最佳决策。那么整体的复杂度就变成了状态数是n，决策数是logN，最后的复杂度就是 O(nlogn) 。
我们来看下代码：
总结
到这里，这道题就讲解完了，整个题目的精髓在于我们维护了一个有序的数组，使得我们可以通过二分查找来找到每个状态的最佳决策。说来惭愧这道题我做过好几次，但是之前很多次都记不住解法，过段时间就会忘记，后来我才找到了诀窍。我们不能死记算法运行的原理，这样下次遇到了变体我们也做不出来。我们必须要理解这个优化出现的原因，推导的前因后果，这样我们才有能力推导其他的问题。
所以希望大家都能把这个推导的过程想明白，而不是只停留在我们怎么运用二分进行优化上。关于这道题还有其他的变种，举个例子，比如如果我们想要求出最少需要几套导弹系统能够拦截所有的导弹，应该怎么做呢？这个问题留给大家思考。我想如果能能够理解上面的做法，应该不难想出答案。
今天的文章就是这些，如果觉得有所收获，请顺手点个关注或者转发吧，你们的举手之劳对我来说很重要。
