牛牛的数列(牛客网)

题目链接:https://ac.nowcoder.com/acm/problem/13142

题目描述：

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

输入描述：

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

输出描述：

输出一个整数,表示最长的长度。

示例：

输入：
6 
7 2 3 1 5 6

输出：
5

题目分析：

本题定义两个数组，

一个记录当前位置以前递增数列的个数，一个记录当前位置以后递增数列的个数

通过两次遍历，

一次从头开始，一次从尾开始，得出两个数列。

最后再遍历一遍判断当前位置的后面一个数减去前面一个数是否小于2判断两数列是否连续得出答案。

代码：

c++:

#pragma warning(disable:4996)
#include<iostream>
const int inf = 10e9;
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int main()
{
    int n, ans = 1;
    scanf("%d", &n);
    int* a = new int[n + 2];
    int* greater = new int[n + 1];
    int* less = new int[n + 2];
    greater[0] = 0;
    less[n + 1] = 0;
    a[0] = inf, a[n + 1] = 0;
    for (int i = 1;i <= n;i++)
    {
        a[i] = read();
        if (a[i - 1] < a[i])
            greater[i] = greater[i - 1] + 1;
        else
            greater[i] = 1;
    }
    for (int i = n;i >= 1;i--)
    {
        if (a[i] < a[i + 1])
            less[i] = less[i + 1] + 1;
        else
            less[i] = 1;
    }
    int tem;
    for (int i = 1;i <= n;i++)
    {
        ans = std::max(ans, greater[i - 1] + 1);
        ans =std::max(ans, less[i + 1] + 1);
        if (a[i + 1] - a[i - 1] >= 2)
            ans = std::max(ans, greater[i - 1] + less[i + 1] + 1);
    }
    printf("%d", ans);
}