数组切分
作者:
husheng
,
2022-05-18 12:43:34
,
所有人可见
,
阅读 230
//如果一个区间内末位-初始位的下标=最大值-最小值,那么这个区间内的数字可以组成一段连续的数
import java.util.Scanner;
public class 数组切分 {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] arr=new int[n+5];
for(int i=1;i<=n;i++) {
arr[i]=input.nextInt();
}
//dp[i]表示从第1位到第i位的集合数量
int[] dp=new int[n+5];
dp[0]=1;
for(int i=1;i<=n;i++) {
int max=arr[i];
int min=arr[i];
for(int j=i;j>=1;j--) {
max=Math.max(max, arr[j]);
min=Math.min(min, arr[j]);
if(max-min==i-j) {
dp[i]=(dp[i]+dp[j-1])%1000000007;
}
}
}
System.out.println(dp[n]);
}
}