爱奇艺 爬山收集钻石问题 算法岗 编程题第一题

    /*爱奇艺，算法第一题,f(i)=f(i-1)+max(dia[i][上],dia[i][左上])*/
    public static int climb(int[][] num, int n) {
        if (num.length == 0)
            return 0;
        //输入时从山顶开始的，需要先转换使得小坐标是山底，这里注意从山底到山顶爬山的过程，
        //更从山顶到山底下山的过程不同！
        int[][] dia = new int[n][n];
        for (int i = 0; i < num.length; i++) {
            dia[i] = num[n - i - 1];
        }

        //f(0)初始值不确定，所以遍历所有起点，最终选择最大值的路径
        int result = 0;
        for (int m = 0; m < n; m++) {
            int[] sum = new int[n]; //sum[i]表示爬i层的最大直
            int[] max_index = new int[n]; //每行走点的下标

            max_index[0] = m;

            sum[0] = dia[0][max_index[0]];

            for (int i = 1; i < n; i++) {
                max_index(dia, max_index, i);
                if (max_index[i] + 1 < 0)
                    sum[i] = sum[i - 1] + Math.max(dia[i][max_index[i]], dia[i][max_index[i] + 1]);
                else
                    sum[i] = sum[i - 1] + dia[i][max_index[i]];
            }

            if (sum[n - 1] > result)
                result = sum[n - 1];
        }
        System.out.println("result:" + result);
        return result;

    }

    //更新max_index,存floor层走的那边坐标
    private static void max_index(int[][] num, int[] max_index, int floor) {
        if (max_index[floor - 1] - 1 < 0)
            max_index[floor] = max_index[floor - 1];
        else if (max_index[floor - 1] >= num[floor].length) {
            max_index[floor] = max_index[floor - 1] - 1;
        } else {
            int a = num[floor][max_index[floor - 1]];
            int b = num[floor][max_index[floor - 1] - 1];
            max_index[floor] = a <= b ? max_index[floor - 1] - 1 : max_index[floor - 1];
        }
    }