小红书笔试

public int pathSum(int[][] array) {
        int[][] dp = new int[array.length][array[0].length];
        for (int i = 0;i < array[0].length;i++) {
            dp[0][i] = array[0][i];
        }

        for(int i = 1;i < array.length;i++) {
            for(int j = 0;j < array[0].length;j++) {
                dp[i][j] = dp[i - 1][j];
                if(j > 0) {
                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - 1]);
                }
                if(j != array[0].length - 1) {
                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j + 1]);
                }
                dp[i][j] += array[i][j];
            }
        }
        int ans = 0;
        for(int i = 0;i < array[0].length;i++) {
            ans = Math.max(ans,dp[array.length - 1][i]);
        }
        return ans;
    }

public static void main(String[] args) {
        int N = 0;
        int k = 0;
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        k = sc.nextInt();
        int[] nums = new int[N];
        for(int i = 0;i < N;i++) {
            nums[i] = sc.nextInt();
        }
        Arrays.sort(nums);
        int left = 0;
        int right = nums[nums.length - 1] - nums[0];
        while(left < right) {
            int mid = (left + right + 1) >> 1;
            if(check(nums,k,mid)) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        System.out.println(left);
    }

    private static boolean check(int[] nums, int k, int mid) {
        int res = 1;
        int last = nums[0];
        for(int i = 1;i < nums.length;i++) {
            if(nums[i] - last >= mid) {
                res++;
                last = nums[i];
            }
        }
        return res >= k;
    }