NC13134牛牛的数列（动态规划）

链接：https://ac.nowcoder.com/acm/problem/13134

来源：牛客网

题目描述

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

输入描述:

输入包括两行,第一行包括一个整数n(1 ≤ $nn$ ≤ 10^5),即数列的长度; 第二行n个整数$a_{i}a\_i$, 表示数列中的每个数(1 ≤ $a_{i}a\_i$ ≤ 10^9),以空格分割。

输出描述:

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

示例1

输入

6 7 2 3 1 5 6

输出

5

思路

$lhs[i]lhs[i]$表示从左往右以$a[i]a[i]$为终止元素的最长连续上升序列的长度。

$rhs[i]rhs[i]$表示从右往左以$a[i]a[i]$为起始元素的最长连续上升序列的长度。

先用两次循环求出$lhs[i]lhs[i]$和$rhs[i]rhs[i]$

再对$a[i]a[i]$从左往右进行判断，取最大值：

maxn = max(maxn, max(lhs[i], rhs[i])); 
//以该点为起或终点的连续上升序列的最长长度。

if (a[i - 1] < 1e9) {
	maxn = max(maxn, lhs[i - 1] + 1);
}
//如果该点不与前面的上升序列连续，若修改后的数未大于规定范围，则修改该点使其为前面上升序列的终点，并满足连续上升序列，取最长。

if (a[i + 1] > 1) {
	maxn = max(maxn, rhs[i + 1] + 1);
}
//如果该点不与后面的上升序列连续，若修改后的数未小于规定范围，则修改该点使其为后面上升序列的起点，并满足连续上升序列，取最长。

if (a[i + 1] - a[i - 1] >= 2) { //如果能够修改来满足连续上升
	maxn = max(maxn, lhs[i - 1] + rhs[i + 1] + 1);
}

AC代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int a[N];
int lhs[N], rhs[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    for (int i = 1; i <= n; i++) {
        if (a[i] > a[i - 1]) {
            lhs[i] = lhs[i - 1] + 1;  
        } 
        else {
            lhs[i] = 1;  
        } 
    }
    for (int i = n; i >= 1; i--) {
        if (a[i] < a[i + 1]) {
            rhs[i] = rhs[i + 1] + 1;  
        } 
        else {
            rhs[i] = 1;
        } 
    }
    
    int maxn = 1;
    for (int i = 1; i <= n; i++) { 
        maxn = max(maxn, max(lhs[i], rhs[i]));
        if (a[i - 1] < 1e9) {
        	maxn = max(maxn, lhs[i - 1] + 1);
        }
        if (a[i + 1] > 1) {
        	maxn = max(maxn, rhs[i + 1] + 1);
        }
        if (a[i + 1] - a[i - 1] >= 2) {
            maxn = max(maxn, lhs[i - 1] + rhs[i + 1] + 1);  
        } 
    }
    cout << maxn << endl;
    return 0;
}