最大半径问题 - James Pan - 博客频道 - CSDN.NET

最大半径问题 - James Pan - 博客频道 - CSDN.NET
一个长度为n的数组，从中选取k个数字，若定义这k个数字的半径为排序后相邻两个数字之间的最小间隔，则k个数字所能达到的最大半径是多少？
如果k = 1，则半径为无穷大。

假设k > 0。

方法一：深度优先搜索。

class SolutionDFS {
 private int max = 0;
 public SolutionDFS(int[] nums, int k) {
  find(nums, 0, 0, k, 0);
 }
 private void find(int[] nums, int from, int step, int k, int min) {
  if (step == k) {
   max = Math.max(max,  min);
  } else if (step == 0) {
   find(nums, 1, step + 1, k, Integer.MAX_VALUE);
  } else if (step == k - 1) {
   find(nums, nums.length, step + 1, k, Math.min(min, nums[nums.length - 1] - nums[from - 1]));
  } else if (min > max) {
   for(int i = from; i + (k - step) <= nums.length; i++) {
    find(nums, i + 1, step + 1, k, Math.min(min, nums[i] - nums[from - 1]));
   }
  }
 }
 public int getSolution() {
  return max;
 }
}

方法二：递归+记忆化搜索。

class SolutionRecursive {
 
 private boolean[][] visit;
 private int[][] dp;
 private int[] nums;
 
 public SolutionRecursive(int[] nums, int k) {
  int n = nums.length;
  this.visit = new boolean[n + 1][k + 1];
  this.dp = new int[n + 1][k + 1];
  this.nums = nums;
  dp(n, k);
 }
 
 public int getSolution() {
  int n = dp.length - 1;
  int k = dp[n].length - 1;
  return dp[n][k];
 }
 
 private int dp(int n, int k) {
  if (visit[n][k]) return dp[n][k];
  visit[n][k] = true;
  if (n < k || k == 0) {
   dp[n][k] = 0;
   return dp[n][k];
  }
  if (k == 1) {
   dp[n][k] = Integer.MAX_VALUE;
   return dp[n][k];
  }
  int result = dp(n - 1, k);
  for(int i = k - 1; i < n; i++) {
   result = Math.max(result, Math.min(dp(i, k - 1), nums[n - 1] - nums[i - 1]));
  }
  dp[n][k] = result;
  return result;
 }
}

方法三：递推+动态规划。

class SolutionIterative {
 private int solution;
 
 public SolutionIterative(int[] nums, int k) {
  int[][] radius = new int[nums.length + 1][k + 1];
  for(int i = 1; i <= nums.length; i++) {
   radius[i][1] = Integer.MAX_VALUE;
   for(int j = 2; j <= k; j++) {
    radius[i][j] = radius[i - 1][j];
    for(int m = j - 1; m < i; m++) {
     radius[i][j] = Math.max(radius[i][j], Math.min(radius[m][j - 1], nums[i - 1] - nums[m - 1]));
    }
   }
  }
  solution = radius[nums.length][k];
 }
 
 public int getSolution() {
  return this.solution;
 }
}

Read full article from 最大半径问题 - James Pan - 博客频道 - CSDN.NET