题解 | #牛妹的面试#

思路：

题目的主要信息：

• 凸子序列：对于子序列中的,使得所有
• 单调递增或单调递减序列也算凸序列
• 单独一个数是长度为1的凸序列
• 序列数大于0，不用考虑特殊情况
• 求一个序列中的最长凸子序列长度

其实这就是两个最长递增子序列问题的叠加， 从左往右是找一个最长递增子序列，从右往左也是找一个最长递增子序列，两个子序列长度和减去这个重复计算了一次的即可得到最长凸子序列长度。

方法一：动态规划
具体做法：
用两个辅助数组left与right，left记录从左往右的每个元素的最长递增子序列长度，right记录从右往左的每个元素的最长递增子序列长度，遍历数组每个元素，比较，找到一个最大值。

class Solution {
public:
    int mountainSequence(vector<int>& numberList) {
        int n = numberList.size();
        vector<int> left(n, 1);
        vector<int> right(n, 1);
        int res = 1;
        for(int i = 1; i < n; i++) {  //从左往右，第i个数结尾的连续上升子序列长度
            for(int j = 0; j < i; j++){
                if(numberList[i] > numberList[j])
                    left[i] = max(left[i], left[j] + 1);
            }
        }
        for(int i = n - 2; i >= 0; i--){  //从右往左，第i个数结束的连续上升子序列长度
            for(int j = n - 1; j > i; j--)
                if(numberList[i] > numberList[j])
                    right[i] = max(right[i], right[j] + 1);
        }
        for(int i = 0; i < n; i++){ //比较每一个值
            res = max(res, left[i] + right[i] - 1);
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，遍历辅助数组left和right，都两层循环
• 空间复杂度：，两个辅助数组的空间

方法二：二分法改进
具体做法：
在填充left及right数组的时候我们可以用二分法进行改进：
建立一个辅助数组dp，其中表示长度为的最长递增子序列结尾元素的最小值，dp数组是一个递增序列，只有它的结尾元素越小，后面递增长度才会更多。而这个递增辅助数组的长度就是当前最长的递增子序列的长度。

class Solution {
public:
    int mountainSequence(vector<int>& numberList) {
        int n = numberList.size();
        if(n <= 2) 
            return n;
        int res = 1;
        vector<int> left(n);
        vector<int> right(n);
        vector<int> dp(1,0);  //递增序辅助数组
        left[0] = 1;
        for(int i = 0; i < n; i++){ //左边最长递增子序列长度
            if(numberList[i] > dp.back()){
                dp.push_back(numberList[i]); //O(1)
            }else{
                auto iter = lower_bound(dp.begin(), dp.end(), numberList[i]); //O(logn)
                *iter = numberList[i];
            }
            left[i] = dp.size() - 1;
        }
        dp.resize(1);  //还原辅助数组，处理右边
        dp[0] = 0;
        right[0] = 1;
        for(int i = n - 1; i >= 0; i--){
            if(numberList[i] > dp.back()){
                dp.push_back(numberList[i]);
            }else{
                auto iter = lower_bound(dp.begin(), dp.end(), numberList[i]);
                *iter = numberList[i];
            }           
            right[i] = dp.size() - 1;
        }
        for(int i = 0; i < n; i++){
            res = max(res, left[i] + right[i] - 1);
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，一次遍历，其中lower_bound为二分查找函数
• 空间复杂度：，三个一维辅助数组