题目描述
已知一个长度为 N的数组:A1,A2,A3,…AN恰好是 1∼N的一个排列。
现在要求你将 A数组切分成若干个 (最少一个,最多 N个)连续的子数组,并且每个子数组中包含的整数恰好可以组成一段连续的自然数。
样例
4
1 3 2 4
算法1
(动态规划) $O(n^2)$
-
f[i]
: 这个数组表示以a[i]
结尾的切分合法数组的方法数量。在代码中,f[i]
存储的是以a[i]
结尾的切分合法数组的方法数量。 -
外层循环遍历数组
a
,从第一个元素到最后一个元素,依次计算以当前元素结尾的合法切分数量。 -
内层循环从当前位置往前遍历,检查以当前元素结尾的连续子数组是否能够构成一段连续的自然数。如果满足条件,则更新以当前位置结尾的合法切分数量。具体来说:
- 维护当前连续子数组的最大值
max
和最小值min
。 - 如果当前子数组的最大值与最小值之差等于子数组长度减一(即当前子数组构成了连续的自然数序列),那么以当前位置结尾的合法切分数量
f[i]
就加上以上一个最小值的位置结尾的合法切分数量f[j - 1]
。 -
最后结果要对
mod
取模。 -
最终输出
f[n]
,即以整个数组a
的最后一个元素结尾的合法切分数量。
import java.util.Scanner;
public class Main {
static int mod = 1000000007;
public static void main(String[] args) {
// f[i]: 以a[i]结尾的切分合法数组的方法数量
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 = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
for (int j = i; j > 0; j--) {
max = Math.max(max, a[j]);
min = Math.min(min, a[j]);
//如果a[j, i]是一段连续的自然数,那么就有以a[i]结尾的合法切分合法数量+=以a[j - 1]结尾的合法切分数量
//即f[i] += f[j - 1]
if (max - min == i - j)
f[i] = (f[i] + f[j - 1]) % mod;
}
}
System.out.println(f[n]);
}
}