版权声明：本文为博主原创文章未经博主允许不得转载。 /u/article/details/

更新最长时，并且记录前一个的下标

最后倒过来存，然后输出

这道题目可以用贪心和动态规划求解其实两种方法都是想通的。

贪心思想：对于每个飞来的导弹查找能够打到它的，飞得最低的防御系统如果没有，则加入一个新防御系统

动态规划思想：就是求最长上升子序列。

会发现贪心方法的思想和动态规划方法的思想是一样的。

上面代码求的其实是最长仩升子序列

如果对比求最长上升子序列的O（nlogn）复杂度的贪心算法+二分法，会发现上面的贪心思想其实就是求最长上升子序列的O（nlogn）复杂喥的贪心算法+二分法的思想中的二分法换成了线性查找也就是说，上面的贪心思想其实就是求最长上升子序列

所以这道题目可以用动態规划来求最长上升子序列。