牛牛的数列

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
int a[100005];
int b[100005];	//正向连续上升长度
int c[100005];	//反向连续下降长度
int main()
{
	int n,i,j,k;
	while(~scanf("%d",&n))
	{
		memset(b,0,sizeof b);
		memset(c,0,sizeof c);
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		b[1]=1;
		for(i=1;i<n;i++)
			if(a[i]<a[i+1])
				b[i+1]=b[i]+1;
			else
				b[i+1]=1;
		c[n]=1;
		// puts("hhh");
		for(i=n;i>1;i--)
			if(a[i]>a[i-1])
				c[i-1]=c[i]+1;
			else
				c[i-1]=1;
		// for(i=1;i<=n;i++)
			// printf("%d,",b[i]);
		// puts("");
		// for(i=1;i<=n;i++)
			// printf("%d,",c[i]);
		// puts("");
		int ans=0;
		for(i=1;i<n;i++)
		{
			if(a[i]>a[i+1])	//a[i]和a[i+1]处出现跳跃
			{
				if(a[i+1]-2>=a[i-1])	//若修改a[i]能消除跳跃
					ans=max(ans,b[i-1]+c[i+1]+1);
				if(a[i]+2<=a[i+2])	//若修改a[i+1]能消除跳跃
					ans=max(ans,b[i]+c[i+2]+1);
				ans=max(ans,max(b[i],c[i+1])+1);	//此处是
			}
		}
		for(i=1;i<=n;i++)	//未出现跳跃，取所有连续上升最大值
			ans=max(ans,max(b[i],c[i]));
		printf("%d\n",ans);
	}
	return 0;
}
/*
12
7	2	3	4	5	6	7	4	9	10	11	12
1	1	2	3	4	5	1	2	3	4	5	6
1	5	4	3	2	1	6	5	4	3	2	1
11

3
1 2 3
3

1
3
1

12
7	2	3	4	5	9	9	8	9	10	11	12
1	1	2	3	4	5	1	1	2	3	4	5
1	5	4	3	2	1	1	5	4	3	2	1
6
*/

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 1E5;
int n;
int arr[MAX_N];

int main(int argc, char *argv[])
{
	cin >> n;
	int maxLen[n];
	for(int i=0;i<n;i++){
		cin >> arr[i];
		maxLen[i] = 1;
	}
	for (int i = 1; i < n; ++i)
	{
		bool flag = true;
		for (int j = i-1; j >= 0 ; --j)
		{
			if (arr[j] < arr[j+1])
			{
				maxLen[i]++;
			}else{
				if (j-1>=0 && arr[j+1]-arr[j-1]>=1 && flag)
				{
					maxLen[i]++;
					j--;
					flag = false;
				}else if(j+2<n && arr[j+2]-arr[j]>=1 && flag){
					flag = false;
				}else{
					break;
				}
			}
		}
	}
	sort(maxLen,maxLen+n);
	cout << maxLen[n-1]+1 << endl;
	return 0;
}

import sys

def Main(strs):
	n = int(strs)
	li = map(int,sys.stdin.readline().strip().split())
	if n == 1:
		return 1
	num = []
	count = 1
	maxval = 0
	for i in xrange(1,n):
		if li[i]<=li[i-1]:
			num.append(count)
			count = 0
		count += 1
	if count !=0:
		num.append(count)
	if len(num) == 1:
		return num[0]
	sumval = 0
	for i in xrange(len(num)-1):
		sumval += num[i]
		if num[i+1] != 1:
			if (li[sumval-1]+1<li[sumval+1] or li[sumval-2]+1<li[sumval]) and num[i] + num[i+1] > maxval:
				maxval = num[i]+ num[i+1]
		else:
			if num[i] + 1 > maxval:
				maxval = num[i]+ num[i+1]
	return maxval
while True:
	strs = sys.stdin.readline().strip()
	if not strs:
		break
	print Main(strs)

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] a=new int[n+2];//分别为序列的首尾留一位，下面输入时起始赋值是a[1],结束是a[n],所以a[0],a[n+1]会被默认初始化为0，即a[0]=0,a[n+1]=0
            for (int i=1;i<=n;i++){
                a[i]=sc.nextInt();
            }
            int[] left = new int[n+1];//记录正序遍历找出递增的各个子序列长度
            int[] right = new int[n+2];//记录逆序遍历找出递增的各个子序列长度
            for (int i=1;i<=n;i++){//正向统计连续递增序列的长度（以第i位数结尾的递增子序列）
                left[i] = a[i-1]<a[i]?left[i-1]+1:1;//i=1时，a[0]=0<1<=a[1](因为要求数据1 ≤ a_i ≤ 10^9)，left[0]默认初始化为0，则left[1]=1
            }
            for (int j=n;j>0;j--){//逆向统计连续递增序列的长度（以第i位数开始的递增子序列）
                right[j] = a[j]<a[j+1]?right[j+1]+1:1;//j=n时，a[n]>=1>a[n+1]=0，right[n+1]默认初始化为0，则right[n]=1
            }
            int result=1;//最小的序列长度为1，所以把result初始化为1
            for(int i=1;i<=n;i++){//加1是算上第i位数的长度.对于每一位置i有左侧到它最长的连续子序列长度left[i] 右侧有连续递增子序列长度right[i]
                //此处是为了比较result、left[i-1]+1、right[i+1]+1的最大值，并赋给result
                result=Math.max(result,left[i-1]+1);
                result=Math.max(result,right[i+1]+1);
                if(a[i+1]-a[i-1]>=2){//第i+1位与第i-1位至少相差2位，则可以修改第i位数，使第i-1、i、i+1也可以组成连续递增序列。
                    result = Math.max(result,left[i-1]+right[i+1]+1);//查找两个和的最大值
                }
            }
            System.out.println(result);
        }
    }
}

/*
解题思路:
动态规划+判断。
以v[i]开始的最长上升子序列dp1, v[i]<v[i+1]时，dp1[i] = dp1[i+1]+1;否则dp1[i]=1;
以v[i]结尾的最长上升子序列dp2, v[i]>v[i-1]时，dp2[i] = dp2[i-1]+1;否则dp2[i]=1;
对于每一个位置i
i=0时，maxLen=dp1[1]+1
i=n-1时，maxLen = dp2[n-2]+1
其他:
v[i-1]+1 < v[i+1], maxLen = dp1[i+1]+dp2[i-1]+1否则：
maxLen = max(dp1[i+1],dp2[i-1])+1
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> v(n, 0);
        for (int i = 0; i < n; ++i)
            cin >> v[i];
        if (n == 0 || n == 1)
        {
            cout << n << endl;
            continue;
        }
        vector<int> dp1( n, 0 ); //dp1[i]是以v[i]开始的最长上升子序列
        vector<int> dp2( n, 0 ); //dp2[i]是以v[i]结尾的最长上升子序列

        dp1[n - 1] = 1;
        for (int i = n - 2; i >= 0; --i)
        {
            if (v[i] < v[i + 1])
                dp1[i] = dp1[i + 1] + 1;
            else
                dp1[i] = 1;
        }

        dp2[0] = 1;
        for (int i = 1; i < n - 1; ++i)
        {
            if (v[i] > v[i - 1])
                dp2[i] = dp2[i - 1] + 1;
            else
                dp2[i] = 1;
        }

        int ret = 1;
        int m = 1;
        for (int i = 0; i < n - 1; ++i)
        {
            if (i == 0)
                m = dp1[i + 1] + 1;
            else if (i == n - 1)
                m = dp2[i - 1] + 1;
            else if (v[i - 1] + 1 < v[i + 1])
                m = dp1[i + 1] + dp2[i - 1] + 1;
            else
                m = max(dp1[i + 1], dp2[i - 1]) + 1;
            if (m > ret)
                ret = m;
        }

        cout << ret << endl;
    }

}

import java.util.*;

public class test20170522F {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int N = sc.nextInt();
			int[] a = new int[N];
			int[] maxLen = new int[N];
			for(int i=0;i<N;i++){
				a[i] = sc.nextInt();
			}
			//对a[0]特殊处理
			if (a[1] >= 2) {
				maxLen[0] = 2;
				for (int i = 2; i < N; i++) {
					if (a[i] > a[i - 1])
						maxLen[0]++;
					else
						break;
				}
			}
			//对a[N-1]特殊处理
			maxLen[N - 1] = 2;
			for (int i = N - 2; i >= 0; i--) {
				if (a[i] > a[i - 1])
					maxLen[N - 1]++;
				else
					break;
			}
			//对标号是1~N-2的进行处理
			for (int i = 1; i <= N - 2; i++) {
				if (a[i + 1] - a[i - 1] >= 2) {
					maxLen[i] = 3;
					for (int j = i - 1; j > 0; j--) {
						if (a[j] > a[j - 1])
							maxLen[i]++;
						else
							break;
					}
					for (int j = i + 1; j < N-1; j++) {
						if (a[j + 1] > a[j])
							maxLen[i]++;
						else
							break;
					}
				} else
					maxLen[i] = 2;
			}
			Arrays.sort(maxLen);
			System.out.println(maxLen[N-1]);
		}
	}

} 

预处理+枚举

先预处理出和数组，表示以元素结尾的递增序列长度；表示以元素开头的递减序列长度。

然后枚举要修改的位置，检查和能不能接起来就可以了，维护最大值。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, a[N], left_i[N], right_d[N];

int main() {
    scanf("%d", &n);
    if(n == 1) {
        puts("1");
        return 0;
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        left_i[i] = right_d[i] = 1;
    }
    for(int i = 1; i < n; i++) {
        int j = n - 1 - i;
        if(a[i] > a[i - 1]) left_i[i] = left_i[i - 1] + 1;
        if(a[j] < a[j + 1]) right_d[j] = right_d[j + 1] + 1;
    }
    int ans = max(1 + right_d[1], 1 + left_i[n - 2]);
    for(int i = 1; i < n - 1; i++) {
        if(a[i + 1] - a[i - 1] > 1) {
            ans = max(ans, 1 + left_i[i - 1] + right_d[i + 1]);
        }else {
            ans = max({ans, left_i[i], right_d[i]});
        }
    }
    printf("%d", ans);
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for(int i=0;i<n;++i) {
            array[i] = sc.nextInt();
        }
        // 以array[i]结尾的连续序列长度
        int[] left = new int[n];
        // 以array[i]开头的连续序列长度
        int[] right = new int[n];
        int res = 0;
        left[0] = 1;
        right[n-1] = 1;
        for(int i=1;i<array.length;++i) {
            if(array[i]>array[i-1]) {
                left[i] = left[i-1]+1;
            } else {
                left[i] = 1;
            }
        }
        for(int i=n-2;i>=0;--i) {
            if(array[i]<array[i+1]) {
                right[i] = right[i+1]+1;
            } else {
                right[i] = 1;
            }
        }
        for(int i=1;i< array.length-1;++i) {
            if(array[i-1]+1<array[i+1]) {
                int sum = left[i-1]+right[i+1]+1;
                if(sum>res) {
                    res = sum;
                }
            }
        }
        // 只改变头、尾可以达到的最大结果
        res = Math.max(res, 1+right[1]);
        res = Math.max(res, 1+left[n-2]);
        System.out.println(res);
    }
}

思路

分析：这道题目看上去没法下手，就当学习一个思路吧，首先根据当前数组顺着求一遍以每个位置作为结尾的连续最长递增子序列的长度值，再逆着求解以每个元素作为开头的连续最长递增子序列的长度值，然后根据这两组值来找连接点。具体就拿体重的例子来说，此时数组arr为
7 2 3 1 5 6，我们定义两个数组left
和right，left数组表示正着求以每个元素作为结尾的最长递增子序列的长度，而right数组表示逆着以每个元素作为开头的连续最长递增子序列的长度值，所以可以知道left[0]=1,表示以7结尾的目前最长的连续递增子序列的长度值就是1，依次left[1]=1,left[2]=2,left[3]=1,left[4]=2,left[5]=3;
而right[5]=1,right[4]=2,right[3]=3,right[2]=1,right[1]=2,right[0]=1;好了，到此为止两个辅助的数组已经求出，接下来就要找连接点了，是这样的，根据题目意思，我们要找一个子序列，而且之多改变一个数就可以形成严格的连续递增子序列，所以我们先盯住数组中2这个数，我们发现以7结尾的最长的连续递增子序列的长度为left[0],而以3开头的连续递增子序列长度为right[2]，这样，我们其实不用管7和3之间的数到底是多少，是2也好，不是2也好，只要2前面的数7能够严格小于2后面的数3，说明通过改变7和3之间这个数至合适的数值则，这两部分就可以连成一个连续的严格递增子序列，所有，我们遍历所有这样的点，记录满足条件的最大的长度再加1即可。https://blog.csdn.net/wwe4023...

代码

let n = parseInt(readline());
let t1 = readline();
let t2 = new String(t1);
let line = t2.split(" ");
let arr =  new Array();
for(let i = 0; i < line.length; i++){
    arr[i] = parseInt(line[i]);
}
let left = new Array(n);//以arr[i]结尾的连续序列长度
let right = new Array(n);//以arr[i]开头的连续序列长度
let ans = 0;
left[0] = 1;
right[0] = 1;
for(let i = 1; i < arr.length; i++){
    if(arr[i] > arr[i-1]){
        left[i] = left[i-1] + 1;
    }else{
        left[i] = 1;
    }
    //left[i] = computeLeft(i, arr);
}
for(let i = arr.length - 1; i >= 0; i--){
    if(arr[i] < arr[i+1]){
        right[i] = right[i+1]+1;
    }else{
        right[i] = 1;
    }
    //right[i] = computeRight(i, arr);
}
for(let i = 1 ; i < arr.length-1; i++){
    if(arr[i-1] <  arr[i+1]){
        let sum = left[i-1] + right[i+1];
        if(sum > ans){
            ans = sum;
        }
    }
}

print(ans+1);

import java.util.Scanner;

/*
 * 参考大神的解题思路：http://www.cnblogs.com/olivegyr/p/6984519.html
 * 设置left，right两个数组,left[i]表示以i为结束的最长连续递增子串的长度,right[i]表示以i开始的最长连续递增子串的长度；
 * 然后针对i~n-1,如果nums[i-1]<nums[i+1],则取left[i-1]+right[i+1]的最大值
 * */
public class MaxAscSeq {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = scanner.nextInt();
            }

            int[] left = new int[n];
            int[] right = new int[n];
            left[0] = 1;
//            计算left
            for (int i = 1; i < n; i++) {
                if (nums[i] > nums[i - 1]) {
                    left[i] = left[i - 1] + 1;
                } else {
                    left[i] = 1;
                }
            }

//            计算right
            right[n - 1] = 1;
            for (int i = n - 2; i >= 0; i--) {
                if (nums[i] < nums[i + 1]) {
                    right[i] = right[i + 1] + 1;
                } else {
                    right[i] = 1;
                }
            }

            int maxLen = 1;
//            求解结果
            for (int i = 1; i < n - 1; i++) {
                if (nums[i - 1] < nums[i + 1] && maxLen < left[i - 1] + right[i + 1]) {
                    maxLen = left[i - 1] + right[i + 1];
                }
            }
//            添加上中间值
            System.out.println(maxLen + 1);
        }
    }
}

#include <iostream>
using namespace std;
 
const int  N = 100010;
int n;
int a[N];
 
int main()
{
    cin>>n;
    for(int i = 0; i < n ; ++ i) cin>>a[i];
         
    int res = 1,q = 0,p = 0,j1 = 0,j2 = 0,k1 = 0,k2 = 0;
    for(int i = 0; i < n ; ++ i){
        p = 1;
        k1 = i,k2 = i;
        while(a[i] < a[i + 1]) p++, i++, k1++;
        if(!j1|| j1 - j2 + 1 < 2 || k1 - k2 +1 < 2 || a[k2] - a[j1-1] > 1 ||a[k2 + 1] - a[j1] > 1) res = max(res, q + p),i++;
        q = 1;
        j1 = i,j2 = i;
        while(a[i] < a[i + 1]) q++,i++,j1++;
        if(j1 - j2 + 1 < 2 || k1 - k2 +1 < 2  ||a[j2] - a[k1-1] > 1 || a[j2 + 1] - a[k1] > 1) res = max(res,q + p);
    }
    
    cout<<res;
    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int len=sc.nextInt();
        int[] nums=new int[len];
        for(int i=0;i<len;i++){
            nums[i]=sc.nextInt();
        }

        int[] dp=new int[len];
        dp[0]=1;
        int res=0;
        for(int i=1;i<len;i++){
            dp[i]= nums[i]>nums[i-1] ? dp[i-1]+1 : 1;
            res=Math.max(dp[i],res);
        }
        if(res==nums.length) {
            System.out.println(res);
            return;
        }

        res++;

        List<int[]> list=new ArrayList<>();
        for(int i=0;i<len;i++){
            int right=i;
            int left=right-dp[right]+1;
            if(!list.isEmpty()){
                int[] pre=list.get(list.size()-1);
                if(pre[0]==left){
                    pre[1]=right;
                    continue;
                }
            }
            list.add(new int[]{left,right});
        }

        for(int i=0;i<list.size()-1;i++){
            int[] curr=list.get(i);
            int[] next1=list.get(i+1);
            if(next1[0]==next1[1]){
                if(i+2<list.size()){
                    int[] next2=list.get(i+2);
                    if(nums[next2[0]]-nums[curr[1]]>1){
                        res=Math.max(res,next2[1]-curr[0]+1);
                    }
                }
            }else {
                if(nums[next1[0]+1]-nums[curr[1]]>1 || (curr[0]!=curr[1] && nums[next1[0]]-nums[curr[1]-1]>1)){
                    res=Math.max(res,next1[1]-curr[0]+1);
                }
            }
        }
        System.out.println(res);
    }
}

'''
链接：https://www.nowcoder.com/questionTerminal/4e1012fe691b446d88eba5db8f511692
来源：牛客网

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

输入描述:
输入包括两行,第一行包括一个整数n(1 ≤ n ≤ 10^5),即数列的长度;
第二行n个整数a_i, 表示数列中的每个数(1 ≤ a_i ≤ 10^9),以空格分割。

输出描述:
输出一个整数,表示最长的长度。
'''

def lcs(num):
    n = len(num)
    tail = [0]* n #head[i]是以v[i]为开始的最长连续上升子序列
    head = [0]* n #tail[i]是以v[i]为结尾的最长连续上升子序列
    
    tail[0] = 1
    for i in range(1,n):
        if num[i] > num[i-1]:
            tail[i] = tail[i-1]+1
        else:
            tail[i] = 1
    head[n-1] = 1
    for i in range(n-2,-1,-1):
        if num[i+1] > num[i]:
            head[i] = head[i+1]+1
        else:
            head[i] = 1
    res = 1
    for i in range(1,n-1):
        res = max(tail[i],head[i],res)
        if num[i+1]- num[i-1] >= 2:
            res = max(res,head[i+1]+tail[i-1]+1)
    return res

if __name__ == "__main__":
    
    n = int(input())
    num = [int(i) for i in input().split()]
    res = lcs(num)
    print(res)