算法——暴力+优化

本质

这类型题本质就是基于暴力解法，优化其时间复杂度

例题

• 首先容易想到的就是组合型动态规划，可是由于在求以i位置为结尾的最长递增子序列的时候要遍历以[0-i-1]位置为结尾最长递增子序列的长度，所以时间复杂度会达到n^2。
• 要求以i为结尾的最长递增子序列，实际上就是求以[0 - i-1]的元素A谁小于i位置的元素并且以其为结尾的最长递增子序列的长度L最长。对于同一L的，我们只需要保留A较小的哪个（因为同样的效果，能接在它后面肯定更容易），所以每种L的A只有一个，而L为n+1的A一定是接在了L为n的A上，因此L为n+1的A一定比L为n的A大，因此，按照L大小来排列，所有A组成有序的序列，因此我们可以通过二分查找算法（logn）找到i位置新元素最多能插入到谁后面，从而得到长度。也将时间复杂度降低到了n*logn。

• 容易想到的就是暴力枚举第i天卖出可能得到最大利润，从中取最大值。一般思路就是每次枚举第i个位置，都要遍历[0-i-1]求一个最小值，所得的差就是最大利润。时间复杂度是n^2
• 而我们做出的优化就是在枚举第i天卖出的途中就更新[0 - i-1]中的最小值，从而将时间复杂度降低到n