题解 | #牛牛的数列#

题意：

• 给定一个整数序列，取一个连续的子序列，要求满足：最多改变一个数，使该子序列严格上升。

方法一：

解题思路：

• 遍历数组的元素，记为nums[i]，如果nums[i+1]>nums[i-1]+2的话，无论nums[i]为什么数，那么nums[i-1],nums[i],nums[i+1]在最多一次的合理替换中可以变成一个严格上升的序列。寻找到在nums[i]左边以nums[i-1]结束的最长严格上升连续序列，以及在nums[i]右边找到以nums[i+1]开始的最长严格上升连续序列，将两者加起来为一个严格上升连续序列，遍历数组元素nums[i]求出最大值即可。

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return int
     */
    //寻找以i结尾的最长连续严格递增序列长度
    int left(vector<int>& nums,int i){
        int maxLength=1;
        for(int tmp=i;tmp>=1;tmp--){
            if(nums[tmp]>nums[tmp-1])
                maxLength++;
            else 
                break;
        }
        return maxLength;
    }
    //寻找以i开始的最长连续严格递增序列长度
    int right(vector<int>& nums,int i){
        int maxLength=1;
        for(int tmp=i;tmp<=nums.size()-2;tmp++){
            if(nums[tmp]<nums[tmp+1])
                maxLength++;
            else 
                break;
        }
        return maxLength;
    }
    int maxSubArrayLength(vector<int>& nums) {
        int n=nums.size();
        if(n<=2)
            return n;
        int ans=2;
        for(int i=1;i<n-1;i++){
            //改变nums[i]后满足递增条件，则连接前后递增序列
            if(nums[i+1]>=nums[i-1]+2)
                ans=max(ans,left(nums,i-1)+right(nums,i+1)+1);
            //不满足，则只能找单边的递增序列
            else
                ans=max(ans,max(left(nums,i-1)+1,right(nums,i+1)+1));
        }
        //根据起始序列如X,1,X,X 讨论改变第一位和改变最后一位的情况
        if(nums[1]==1)
            //第二位为1，则第一位不可能加入到递增序列中
            ans=max(ans,max(left(nums,n-2)+1,right(nums,1)));
        else
            //其他情况下第一位可以加入到递增序列中
            ans=max(ans,max(left(nums,n-2)+1,right(nums,1)+1));
        return ans;
    }
};

复杂度分析：

时间复杂度：，n为数组nums大小。遍历数组nums，每次遍历执行两次对数组的循环搜索，所以。
空间复杂度：，常数个临时变量。

方法二：

解题思路：

• 针对方法一中的循环调用left()及right()两个函数来求最长递增序列的冗余，可以利用动态规划将递增序列长度值先求出来。

代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return int
     */
    int maxSubArrayLength(vector<int>& nums) {
        int n=nums.size();
        if(n<=2)
            return n;
        int ans=2;
        //初始化left.right数组
        vector<int> left(n,1),right(n,1);
        //left[i]代表以i结尾的最长递增连续子序列长度
        for(int i=1;i<=n-1;i++){
            if(nums[i]>nums[i-1])
                left[i]=left[i-1]+1;
        }
        //right[i]代表以i开始的最长递增连续子序列长度
        for(int i=n-2;i>=0;i--){
            if(nums[i]<nums[i+1])
                right[i]=right[i+1]+1;
        }
        for(int i=1;i<n-1;i++){
            //改变nums[i]后满足递增条件，则连接前后递增序列
            if(nums[i+1]>=nums[i-1]+2)
                ans=max(ans,left[i-1]+right[i+1]+1);
            //不满足，则只能找单边的递增序列
            else
                ans=max(ans,max(left[i-1]+1,right[i+1]+1));
        }
        //根据起始序列如X,1,X,X 讨论改变第一位和改变最后一位的情况
        if(nums[1]==1)
            //第二位为1，则第一位不可能加入到递增序列中
            ans=max(ans,max(left[n-2]+1,right[1]));
        else
            //其他情况下第一位可以加入到递增序列中
            ans=max(ans,max(left[n-2]+1,right[1]+1));
        return ans;
    }
};

复杂度分析：

时间复杂度：，为left，right数组赋值，遍历数组nums也是。
空间复杂度：，left，right数组额外空间。