连续区间的判定

由于数组中的元素是不重复的， 所以有：区间[i,j]中的元素可以组成一段连续的自然数⟺max−min==j−i,其中max为区间中的最大值， min为最小值。证明并不难， 想想就理解了。定义f[i]为区间[1,i]中划分的方法数量。求f[i]时，遍历以i结尾的所有区间[j, i]， 如果[j, i]满足子数组中包含的整数恰好可以组成一段连续的自然数，则[1, i]区间中，将[j, i]划分为一个子数组的方法总数即为f[j−1],先计算f[j - 1],在把(j, i)看成一个片段

import java.util.Scanner;

public class Main {
    static int mod = 1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            int max = a[i], min = a[i];
            /*为什么是倒序
            因为倒序可以保证max和min的有效性，简单来说就是保证
            max和min在(j, i)的最值，采用倒序，从i出发开始判断大小，
            j指针不断向1走每次进行重新比较(比较的两个数就是cur最值)赋值，
            因此可以保证有效性

            但是如果是正序的话，
            一个在左一个在右，并不知道中间的数值是否有最值，故而无法保证最值的有效性
            从而产生小解(少加)
            */
            for (int j = i; j >= 1; j--) {
                max = Math.max(max, a[j]);
                min = Math.min(min, a[j]);
                if (max - min == i - j)
                    f[i] = (f[i] + f[j - 1]) % mod;
            }
        }

        System.out.println(f[n]);
    }
}