题目描述
有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
输入描述:
每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。输出描述:
输出一行表示最大的乘积。
示例1
输入
3 7 4 7 2 50
输出
49
思路：采用动态规划法，即将一个大问题拆分成一个小问题，在小问题的结果为基础上，再添加一个小问题，逐步求解，最终得到结果。
由于考虑到学生能力值取值范围有负数， 所以需考虑成绩的最小值*一个负数有可能变成一个最大值， 所以需要存储最小能力积。
具体实现过程代码中有详细注释。
代码如下：
public class Cholus {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // 学生个数
int[] ability = new int[n]; // 能力
for (int i = 0; i < ability.length; i++) {
ability[i] = input.nextInt();
}
int k = input.nextInt();// 选k个学生
int d = input.nextInt();// 编号差
int[][] maxAbility = new int[n][k]; // maxAbility[i][j]表示 到第i+1个人，取去j+1个学生的最大值
int[][] minAblility = new int[n][k]; // minAblility[i][j]表示 到第i+1个人，取去j+1个学生的最小值
// 当k=1时
for (int i = 0; i < n; i++) {
// 以第i+1个学生为结尾 取出一个，最大能力值即为当前学生能力值
maxAbility[i][0] = ability[i];
// 以第i+1个学生为结尾 取出一个，最小能力值即为当前学生能力值
minAblility[i][0] = ability[i];
}
// 将最大值初始为最小值
int max = Integer.MIN_VALUE;
// 依次以第i+1个学生为结尾，找出最大能力积，知道遍历所有
for (int i = 0; i < n; i++) {
// 当以第i+1个学生为结尾时，假设选出j+1个同学，找出最大能力积
for (int j = 1; j < k; j++) {
// 当以第i+1个学生为结尾，选出j+1个同学时，遍历第i+1个学生的前d个学生，找出最大能力积
for (int p = i - 1; p > Math.max(i - d, 0); p--) {
// 从前d个学生的最大能力积*当前学生能力值中 找出最大能力积
maxAbility[i][j] = Math.max(maxAbility[i][j],
// 在第i+1个学生的 前面学生选j个时的最大能力积和最小能力积分别与当前学生能力值相乘 找出最大值
Math.max(maxAbility[p][j - 1] * ability[i], minAblility[p][j - 1] * ability[i]));
// 从前d个学生的最小能力积*当前学生能力值中 找出最小能力积
minAblility[i][j] = Math.min(minAblility[i][j],
// 在第i+1个学生的 前面学生选j个时的最大值和最小值分别与当前学生能力值相乘 找出最小值
Math.min(maxAbility[p][j - 1] * ability[i], minAblility[p][j - 1] * ability[i]));
}
}
}
// 当选出k个学生时，遍历maxAbility数组找出最大能力积
for (int i = 0; i < n; i++) {
max = Math.max(max, maxAbility[i][k - 1]);
}
System.out.println(max);
}
}