【算法题】牛牛的数列-DP问题

链接：https://ac.nowcoder.com/acm/problem/13142
来源：牛客网

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

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

输出描述:

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

示例1

6 
7 2 3 1 5 6

输出

5

去百度查了下什么叫做“严格上升的子序列”

https://baike.baidu.com/item/%E4%B8%A5%E6%A0%BC%E9%80%92%E5%A2%9E/5318845
递增(increasing)函数是指当函数的任何自变量增加的时候，函数值不减少。严格递增(strongly increasing)是指当函数任何自变量增加的时候函数值也增加。类似地，递减函数(decreasing)是指当函数的任何自变量增加的时候函数值不增加，严格递减(strongly decreasing)是指当函数任何自变量增加的时候函数值却减少。

解题思路：

1. 本题需要考虑间断路径和不间断路径两种场景。所以定义Dep[n]和DepBreak[n]分别表示不间断路径和间断路径。
2. 考虑到执行效率问题，需要从右到左完成动态规划，利用上一次的结果计算本次结果。（亲身尝试，暴力破解会超时）

解题步骤：

1. 对于不间断的情况：在循环遍历第i个数字时，如果第i个数字不大于第i+1个数组（iNums[i]<=iNums[i+1]），则Dep[i]=Dep[i+1]+1，当然，因为这个是不间断的情况，所以DepBreak也要做同样的操作DepBreak[i]=DepBreak[i+1]+1。
2. 对于间断的情况：在循环遍历第i个数字时，如果跨越1个数字后满足要求间断要求，则允许间断计数，即iNums[i]<=iNums[i+2]，跨间断计数。
   间断计数原则：基于无间断的结果Dep[i+2]直接加上2个。
   此时要比较【Dep[i+2]+2】和【按照不间断的方法得到的DepBreak[i]】，大着才是间断情况的最大值。
3. 需要注意：暴力破解会超时、输入个数小于等于2时需要特殊处理。

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

/**
 * @return maxLenth
 */
public class Main20201121_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            // 输入
            Integer n = sc.nextInt();
            Integer[] iNums = new Integer[n];
            Integer[] iDep = new Integer[n];
            Integer[] iDepBreak = new Integer[n];
            for (int i=0; i<n; i++){
                iNums[i] = sc.nextInt();
                iDep[i] = 1;
                iDepBreak[i] = 1;
            }
            // 计算步长
            if (n>2){
                for (int i=n-2; i>=0; i--){
                    // 不间断情况
                    if (iNums[i] <= iNums[i+1]){
                        iDep[i] = iDep[i+1] + 1;
                        iDepBreak[i] = iDepBreak[i+1] + 1;
                    }
                    if (i == n-2 && iNums[i] > iNums[i+1]){
                        iDepBreak[i]++;
                    }
                    // 间断的情况
                    if (i<n-2){
                        if (iNums[i] <= iNums[i+2]){
                            iDepBreak[i] = Math.max(iDep[i+2]+2, iDepBreak[i]);
                        }
                    }
                }
                // 打印结果
                System.out.println(Collections.max(Arrays.asList(iDepBreak)));
            }
            else // n<=2的情况做特殊处理
                // 打印结果
                System.out.println(String.valueOf(n));
        }
    }
}