牛牛的数列-Java-牛客模拟三

关键还是要理解操作过程。

package 模拟三;

import java.util.Scanner;

/**
 * 题目描述：牛牛现在有一个n个数组成的数列,牛牛现在想取一个连续的子序列,并且这个子序列还必须得满足:最多只改变一个数,
 * 就可以使得这个连续的子序列是一个严格上升的子序列,牛牛想知道这个连续子序列最长的长度是多少。
 * 输入描述: 输入包括两行,第一行包括一个整数n(1 ≤ n ≤ 10^5),即数列的长度; 
 * 第二行n个整数a_i, 表示数列中的每个数(1 ≤ a_i ≤ 10^9),以空格分割。
 * 
 * 输出描述: 输出一个整数,表示最长的长度。
 * 
 * 输入例子: 6 
 * 7 2 3 1 5 6
 * 
 * 输出例子: 5
 * 
 * @author 崔洪振367
 * @version 创建时间：2017年5月26日 下午3:32:41
 * 解题思路：给定一个数组a[n+2],其中a[0]和[n+1]是Java中Math中的最大值。
 * 题目要求：找出数组递增序列中最长的一个子序列，其中可以是两段递增的序列的长度和不过中间的一个值可以修改，使其递增序列不变。
 * 1）正序遍历找出递增的最长子序列(preSort[])；
 * 2）逆序遍历找出递增的最长子序列；(sufSort[])（注意也是递增的）
 * 3）整合，找出i位置处的最大值，满足i-1和i+1的差值大于2，就可以也就是Math.max(result, preSort[i-1]+sufSort[i+1]+1);
 */
public class Q2017_7牛牛的数列 {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
//sc.nextLine();
int[] a = new int[n+2];
for(int i=1; i<=n; i++){
a[i] = sc.nextInt();
}

int value = Integer.MAX_VALUE;
a[0] = value;
a[n+1] = value;

int[] preSort = new int[100005];
int[] sufSort = new int[100005];

for(int i=1; i<=n; i++){//正向统计递增的长度
preSort[i] = (a[i-1] < a[i])?preSort[i-1]+1:1;
}

for(int i=n; i>=1; i--){//逆向统计递增的长度
sufSort[i] = (a[i] < a[i+1])?sufSort[i+1]+1:1;
}

int result = 1;
for(int i=1; i<=n; i++){//查找两个的和的最大值，不要忘记加1哟。加1的目的是将i位置处的统计上。
result = Math.max(preSort[i-1]+1, result);
result = Math.max(sufSort[i+1]+1, result);
if(a[i+1]-a[i-1]>=2){
result = Math.max(result, preSort[i-1]+sufSort[i+1]+1);
}
}

System.out.println(result);
}

}

}