题解 | #牛牛的数列#

牛牛的数列

http://www.nowcoder.com/practice/f2419f68541d499f920eac51c63d3f72

牛牛的数列

问题描述：
牛牛现在有一个n个数组成的数列,牛牛现在想取一个连续的子序列,并且这个子序列还必须得满足:最多只改变一个数,就可以使得这个连续的子序列是一个严格上升的子序列,牛牛想知道这个连续子序列最长的长度是多少。
示例
输入：[7,2,3,1,5,6]
返回值：5

方法一

思路分析

通过观察我们会发现，我们要找的满足条件的子序列有一个特点，设置需要改变的数为k，就是k之前的子序列是严格升序的，k之后的子序列也是严格升序的。那么我们考虑对数组从左往右遍历求出每个位置的最长升序子序列长度pre[i]，从右往左遍历求出每个位置从后往前连续降序子序列长度suf[i]，最后遍历整个数组的每个位置i,这时存在三种情况：

初始化满足条件的连续子序列的长度为$max=1$
第i个位置左侧的最长增序子序列长度$max=max\{pre[i - 1] + 1,max\}$
第i个位置右侧的最长增序子序列长度$max=max\{suf[i + 1] + 1,max\}$
由于要找到严格上升的子序列，因此第i个位置前面元素和后面元素的差值必须大于等于2，如果满足严格上升的子序列，则将前后子序列以及自身元素构成最长子序列，此时$max=max\{max,pre[i - 1] + suf[i + 1] + 1\}$

图解

首先构建pre数组和suf数组，此处设置pre数组的长度为n+1，suf数组长度为n+2

$nums=\{7,2,3,1,5,6\}$		7	2	3	1	5	6
	$i=0$	$i=1$	$i=2$	$i=3$	$i=4$	$i=5$	$i=6$	$i=7$
$pre[i]$	0	1	1	2	1	1	2
$suf[i]$		1	2	1	3	2	1	0

C++核心代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return int
     */
    int maxSubArrayLength(vector<int>& nums) {
        // write code here
        int n=nums.size();
        vector<int> temp(n+2);
        temp[0]=INT_MAX;
        temp[n-1]=INT_MAX;
        for(int i=1;i<=n;i++)
        {
            temp[i]=nums[i-1];
        }
        vector<int> pre(n+1);//设置从左到右连续递增子序列的长度
        vector<int> suf(n+2);//设置从右到左连续递减子序列的长度
        pre[0]=0;//第0个元素的子序列长度为0
        suf[n+1]=0;//第n+1个元素的子序列长度为0
        int ans=1;
        for(int i=1;i<=n;i++)
        {
            if(temp[i-1] < temp[i])//升序
            {
                pre[i] = pre[i-1] + 1;//记录当前元素与前一元素的最长升序序列
            }
            else
            {
                pre[i] = 1;//如果当前元素与前面一个元素不存在严格升序，从当前元素自身作为一个子序列
            }
        }
        for(int i=n;i>=1;i--)
        {
            if(temp[i] < temp[i+1])//降序
            {
                suf[i] = suf[i+1] + 1;//记录当前元素与后一元素的最长降序序列
            }
            else
            {
                suf[i] = 1;//如果当前元素与后一个元素不存在严格降序，从当前元素自身作为一个子序列
            }
        }
        for(int i = 1; i <= n; i++)
        {
            ans = max(ans, pre[i - 1] + 1);//第i个位置左侧的最长增序子序列长度
            ans = max(ans, suf[i + 1] + 1);//第i个位置右侧的最长增序子序列长度
            if(temp[i + 1] - temp[i - 1] >= 2)//由于要找到严格上升的子序列，因此第i个位置前面元素和后面元素的差值必须大于等于2
                ans = max(ans, pre[i - 1] + suf[i + 1] + 1);//如果满足严格上升的子序列,则将前后子序列以及自身元素构成最长子序列
        }
        return ans;
    }
};

复杂度分析

时间复杂度分析：存在三个循环遍历，每一个遍历次数为n，因此时间复杂度为$O(n)$
空间复杂度分析: 借助于两个辅助数组，因此空间复杂度为$O(n)$

方法二

思路分析

上面的方法使用了动态规划的办法，采用自下而上的研究思路，从子问题出发，先求出子问题然后将结果保存起来，从而解决更大的问题。因此还可以使用递归的方法，自上而下的研究思路，要求的问题逐渐向下求解直到找到结束的条件，因此使用递归的的办法。

设置满足条件的子序列长度为$ans=1$，这是容易理解的，如果数组不为空，任何一个元素均满足情况
接着遍历数组元素，如果该元素右面的元素减去左面元素大于等于2，则满足严格上升子序列，因此左右子序列以及本身元素可以构成满足条件的子序列，此时$ans=max{ans,pre[i-1]+suf[i+1]+1}$
在递归操作中大的问题为求解$pre[i-1]$，那么继续求解$pre[i-2]$，直到找到开始元素处递归结束
相应的右边子序列递归也如此

C++核心代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return int
     */
    int maxSubArrayLength(vector<int>& nums) {
        // write code here
        int n=nums.size();
        if(n<=0) return 0;
        int ans=1;//初始化一个元素作为子序列
        for(int i = 1; i < n-1; i++)
        {
            if(nums[i + 1] - nums[i - 1] >= 2)//由于要找到严格上升的子序列，因此第i个位置前面元素和后面元素的差值必须大于等于2
                ans = max(ans, pre(i - 1,nums) + suf(i + 1,nums) + 1);//如果满足严格上升的子序列,则将前后子序列以及自身元素构成最长子序列
        }
        return ans;
    }
    
    int pre(int n,vector<int>& nums)//利用递归的思想自上而下求出每一位置的左边最长子序列长度
    {
        if(n==0) return 1;//递归结束的条件,判断是否为数组开始元素
        else if(nums[n]>nums[n-1])//从左往右升序
            return pre(n-1,nums)+1;
        else return 1;
    }
    int suf(int n,vector<int>& nums)
    {
        if(n == nums.size() - 1)//递归结束的条件,判断是否为数组结束元素
            return 1;
        else if(nums[n]<nums[n+1])//从右往左降序
            return suf(n+1,nums)+1;
        else return 1;
    }
};