import java.util.*;
/**
* @author jerryzhuo
* @since 2019/8/24
* 京东合唱团笔试题,时间超时
* 带备忘的动态规划
* 思想是每次找出自数组可以分成的最大组数量
* 比如数组array,如果leftIndex < i < righIndex, 在区间【leftIndex,i -1] 的最大值 < 区间【i,rightIndex】的最小值
* 找出所有的i,然后 result = Max.max(result, dfs(leftIndex,i - 1) + dfs(i, rightIndex))
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//输入
int n = in.nextInt();
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = in.nextInt();
}
//产生结果
Main main = new Main();
System.out.println(main.getResult(array));
}
/**
* ***[i][j] 其中i表示数组的左边,j表示右边
* ***[i][j][0] 表示在这个区间的最小值
* ***[i][j][1] 表示在这个区间的最大值
* ***[i][j][2] 表示在这个区间可以产生多少个分组
*/
private int[][][] ***;
/**
* <逻辑入口>,产生结果
*
* @param array 输入的数组
* @return 可以分成的最多组数量
*/
private int getResult(int[] array) {
*** = new int[array.length][array.length][3];
pojoCache(array);
return dfs(0, array.length - 1);
}
/**
* 生成***
*
* @param array 输入的数组
*/
private void pojoCache(int[] array) {
for (int i = 0; i < array.length; i++) {
***[i][i][0] = array[i];
***[i][i][1] = array[i];
for (int j = i + 1; j < array.length; j++) {
***[i][j][1] = Math.max(array[j], ***[i][j - 1][1]);
***[i][j][0] = Math.min(array[j], ***[i][j - 1][0]);
}
}
}
/**
* @param left array的左区间
* @param right array的有区间
* @return 返回在array[left] ~ array[right] 可以分成的组数量最大值
*/
private int dfs(int left, int right) {
if (right < left) {
return 0;
} else if (***[left][right][2] != 0) {
//一个备忘判断***有就直接返回
return ***[left][right][2];
} else {
int result = Integer.MIN_VALUE;
//i表示分割点
for (int i = left + 1; i <= right; i++) {
int leftMax = ***[left][i - 1][1];
int rightMin = ***[i][right][0];
//如果成立,表示这个区间可以以i进行分割
if (leftMax <= rightMin) {
int newCompare = dfs(left, i - 1) + dfs(i, right);
result = Math.max(result, newCompare);
}
}
//将新的备忘注入***
if (result == Integer.MIN_VALUE) {
***[left][right][2] = 1;
} else {
***[left][right][2] = result;
}
return ***[left][right][2];
}
}
}
#京东##笔试题目##吐槽#