题解 | #牛牛的数列#

import java.util.* ;
public class Main {
    public static void main(String...args) {
        Scanner scan = new Scanner(System.in) ;
        int n = Integer.parseInt(scan.nextLine().trim()) ;
        String arr[] = null ;
        while (scan.hasNextLine()) {
            arr = scan.nextLine().split(" ") ;
        }
        int num[] = new int[n] ;
        for(int i = 0 ; i < n ; i ++) {
            num[i] = Integer.parseInt(arr[i]) ;
        }
        System.out.println(maxLen(num)) ;
    }
    public static int maxLen(int[] num) {
        int len = num.length ;
        //dp1[i]表示以num[i]结尾的最长上升子序列的长度
        int[] dp1 = new int[len] ;
        //dp2[i]表示以num[i]开头的最长上升子序列的长度
        int[] dp2 = new int[len] ;
        //计算dp1
        dp1[0] = 1 ;
        for(int i = 1 ; i < len ; i ++) {
            dp1[i] = 1 ;
            if(num[i] > num[i - 1]) {
                dp1[i] = dp1[i - 1] + 1 ;
            }
        }
        //计算dp2
        dp2[len - 1] = 1 ;
        for(int i = len - 2 ; i >= 0 ; i --) {
            dp2[i] = 1 ;
            if(num[i] < num[i + 1]) {
                dp2[i] = dp2[i + 1] + 1 ;
            }
        }
        //对于num[i]，如果num[i+1] - num[i-1] >= 2 则
        //可以选择改变num[i]得值使得：以num[i]结尾和开头的子序列连接起来
        //形成一个连续的子序列
        //最终的结果是 max(dp1[i],dp2[i],dp1[i]+dp2[i]-1|num[i+1] - num[i-1] >= 2 , dp1[i] + 1 , dp2[i] + 1)
        int maxLen = 1 ;
        for(int i = 0 ; i < len ; i ++) {
            int tmpLen = Math.max(dp1[i] , dp2[i]) ;
            if(i > 0 && i < len - 1 && num[i + 1] - num[i - 1] >= 2) {
                tmpLen = Math.max(tmpLen , dp1[i - 1] + dp2[i + 1] + 1) ;
            }
            if(i > 0) {
                tmpLen = Math.max(tmpLen , dp1[i - 1] + 1) ;
            }
            if(i < len -1) {
                tmpLen = Math.max(tmpLen , dp1[i + 1] + 1) ;
            }
            if(tmpLen > maxLen) {
                maxLen = tmpLen ;
            }
        }
        return maxLen ;
    }
}