本质这类型题本质就是基于暴力解法优化其时间复杂度例题首先容易想到的就是组合型动态规划可是由于在求以i位置为结尾的最长递增子序列的时候要遍历以[0-i-1]位置为结尾最长递增子序列的长度所以时间复杂度会达到n^2。要求以i为结尾的最长递增子序列实际上就是求以[0 - i-1]的元素A谁小于i位置的元素并且以其为结尾的最长递增子序列的长度L最长。对于同一L的我们只需要保留A较小的哪个因为同样的效果能接在它后面肯定更容易所以每种L的A只有一个而L为n1的A一定是接在了L为n的A上因此L为n1的A一定比L为n的A大因此按照L大小来排列所有A组成有序的序列因此我们可以通过二分查找算法logn找到i位置新元素最多能插入到谁后面从而得到长度。也将时间复杂度降低到了n*logn。容易想到的就是暴力枚举第i天卖出可能得到最大利润从中取最大值。一般思路就是每次枚举第i个位置都要遍历[0-i-1]求一个最小值所得的差就是最大利润。时间复杂度是n^2而我们做出的优化就是在枚举第i天卖出的途中就更新[0 - i-1]中的最小值从而将时间复杂度降低到n