小红书笔试
1.常规DP
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;
} 2.二分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;
} 
