Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
796 B
7
Indexable
Never
class Solution {
    public int minimizeMax(int[] nums, int p) {
        if (p == 0) return 0;
        if (nums.length < 2) return -1;
        Arrays.sort(nums);

        // 
        int[] prev = new int[nums.length - 1];
        prev[0] = nums[1] - nums[0];
        for (int i = 1; i < nums.length - 1; i++) {
            prev[i] = Math.min(prev[i-1], nums[i+1] - nums[i]);
        }
        for (int pair = 1; pair < p; pair++) {
            int[] next = new int[prev.length];
            next[0] = Integer.MAX_VALUE;
            next[1] = Integer.MAX_VALUE;
            for (int i = 2; i < next.length; i++) {
                next[i] = Math.min(next[i-1], Math.max(nums[i+1] - nums[i], prev[i-2]));
            }
            prev = next;
        }
        return prev[prev.length - 1];
    }
}