题解 | #牛牛的数列#

思路：

题目的主要信息：

求给定数组的一个子序列，该子序列修改一个元素后可以变成完全递增序列，可以不用修改
要求返回子序列的最长长度

基本思路就是遍历数组中的所有元素，检查如果该元素后一个元素大于前一个元素，我们可以找到以它前一个元素结尾的最长递增序列加上以它后一个元素开始的最长递增序列，二者相加再加上自己就是可修改的最长递增序列。

方法一：递归
具体做法：
我们可以递归得到以 $i-1$ 结束的最长递增序列长度：对于 $i-1$ ，如果 $nums[i-1] > nums[i-2]$ ，则返回子问题 $i-2$ 的基础上加1，否则直接返回1.同理可得到以 $i+1$ 开始的最长递增序列长度。
遍历数组，一旦 $nums[i + 1] >= nums[i - 1]$ ，就可以尝试连接左右两边的最长递增子序列长度。

class Solution {
public:
    int left(int n, vector<int>& nums){  //递归找以n结束的最长递增序列长度
        if(n == 0)
            return 1;
        else if(nums[n] > nums[n - 1])
            return left(n - 1, nums) + 1;
        else
            return 1;
    }
    int right(int n, vector<int>& nums){ //递归找以n开始的最长递增序列长度
        if(n == nums.size() - 1)
            return 1;
        else if(nums[n] < nums[n + 1])
            return right(n + 1, nums) + 1;
        else
            return 1;
    }
    int maxSubArrayLength(vector<int>& nums) {
        int n = nums.size();
        int res = 1;
        for(int i = 1; i < n - 1; i++){ //比较，找到中间点
            if(nums[i + 1] >= nums[i - 1])   
                //左边最长连续上升子序列加上右边
                res = max(res, left(i - 1, nums) + right(i + 1, nums) + 1);
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n^2)$ ，递归为 $O(n)$ ，遍历为 $O(n)$ ，递归在遍历中
空间复杂度： $O(n)$ ，递归栈最大深度可达 $O(n)$

方法二：动态规划
具体做法：
动态规划解决方法一的递归问题：用两个辅助数组，left为以i结尾的最长连续上升子序列的长度，right是以i结尾的最长连续上升子序列的长度。
然后遍历数组，对于每个元素，判断其左右最长连续上升子序列的长度和加1（加本身）是否为最大，返回最大值。
图片说明

class Solution {
public:
    int maxSubArrayLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n + 1);
        vector<int> right(n + 1);
        int res = 1;
        left[0] = 1;
        for(int i = 1; i < n; i++) {  //第i个数结尾的连续上升子序列长度
            if(nums[i] > nums[i - 1]) 
                left[i] = left[i - 1] + 1;
            else 
                left[i] = 1;
        }
        right[n - 1] = 1;
        for(int i = n - 2; i >= 0; i--){    //第i个数开始的连续上升子序列长度
            if(nums[i] < nums[i + 1]) 
                right[i] = right[i + 1] + 1;
            else 
                right[i] = 1;
        }
        for(int i = 1; i < n - 1; i++){ //比较，找到中间点
            if(nums[i + 1] >= nums[i - 1])    
                //左边最长连续上升子序列加上右边
                res = max(res, left[i - 1] + right[i + 1] + 1); 
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，三次遍历，都是单循环
空间复杂度： $O(n)$ ，辅助数组left，right