牛牛的数列

[编程题]牛牛的数列

热度指数：5466 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

6 
7 2 3 1 5 6

输出

算法知识视频讲解

Java

幻之飞雪

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);
    }
}

发表于 2023-01-06 14:25:20 回复(0)