牛客刷题——牛牛的数列

数列"/>

牛客刷题——牛牛的数列

题目：牛牛现在有一个n个数组成的数列,牛牛现在想取一个连续的子序列,并且这个子序列还必须得满足:最多只改变一个数,就可以使得这个连续的子序列是一个严格上升的子序列,牛牛想知道这个连续子序列最长的长度是多少。

eg：输入：[7,2,3,1,5,6]，输出：5

自己的思路是第一次遇到“断口”（导致不是上升子序列的位置）时先忽略，等到第二次遇到断口，那么前面这段数字就构成了一个符合条件的序列，奈何用例只通过了一部分，也不知道是什么原因。。。

然后看了答案解析，

整体思路是首先计算出每个元素作为起始元素所能构成的最长上升子序列，记为right，

然后计算出以每个元素作为终止元素所能构成的最长上升子序列，记为left。

对于 [7,2,3,1,5,6] ，left = [1,1,2,1,2,3]，right = [1,2,1,3,2,1]

由于是想得到一个最长上升的子序列，而且是断口位置使得上升子序列降低了要求（断口位置可以修改，使得本来不是上升的变为上升），而且每个位置都可能是断口，那就需要对每个元素 i 进行遍历，对该元素的前后元素 i-1 和 i+1 进行判断，

如果 nums[ i-1]<nums[i+1]，then great，可以构成一个上升子序列，而且不需要管 i 元素的大小，因为我们有一次修改的机会，这样的话只需要看以 nums[i-1] 为结尾的最长序列和以 nums[i+1] 开头的最长序列即可，两个长度相加再加上 1 就得到最长的序列。

注意这里要将res的初始值定义为1，因为无论如何，只要有数字的话最少也能构成1个上升子序列，对于没有上面情况满足的，如一个完全逆序的数列，这样就只能修改一个数字，最大长度为2，也就是在循环中res不变，还是1，最终返回的时候+1就好了。

完整代码如下：

//版本1public int maxSubArrayLength (int[] nums) {// write code hereif(nums.length==0||nums.length==1) {return nums.length;}int res = 1;int len = nums.length;int[] left = new int[len];  //用于存储每个元素结尾的最长上升子序列长度int[] right = new int[len];//用于存储每个元素开始的最长上升子序列长度left[0]=1;right[len-1] =1;for(int i=1;i<len;i++) {left[i] = nums[i]>nums[i-1]?left[i-1]+1:1;}for(int i=len-2;i>=0;i--) {right[i] = nums[i]<nums[i+1]?right[i+1]+1:1;}for(int i=1;i<len-1;i++) {if(nums[i-1]<nums[i+1]) {int sum = left[i-1]+right[i+1];res = Math.max(res, sum);}}return res+1;}