唉,没办法和东哥做朋友了

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];
        }
    }
}
#京东##笔试题目##吐槽#
全部评论
tql
点赞 回复
分享
发布于 2019-08-24 21:39

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务