题目描述
有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
输入描述:
每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。
输出描述:
输出一行表示最大的乘积。
示例1
输入
37 4 72 50
输出
49
【解决】
① 动态规划！！！！
因为学生能力的输入可能为正也可能为负，因此要使用两个标记数组分别记录最大乘积和最小乘积。
【定义】
max[k][n]表示在最终位置为n时有k个学生的最大乘积； min[k][n]表示在最终位置为n时有k个学生的最小乘积； 【初始化】 max[1][i]=ability[i];位置i上有1个学生的最大乘积为该学生的能力值； min[1][i]=ability[i];位置i上有1个学生的最小乘积为该学生的能力值； 【递推】 max[j][i]=Math.max(max[j][i],Math.max(max[j - 1][pre] * ability[i],max[j - 1][pre] * ability[i])); min[j][i]=Math.min(min[j][i],Math.min(min[j - 1][pre] * ability[i],min[j - 1][pre] * ability[i])); 其中，pre表示上一个计算乘积的位置 【注意】 最大乘积需要遍历每一个满足k个学生的max数组，取最大值。
import java.util.*;
public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()){ int n = sc.nextInt();//学生个数 int[] ability = new int[n + 1]; for (int i = 1;i <= n;i ++){ ability[i] = sc.nextInt(); } int k = sc.nextInt(); int d = sc.nextInt();long[][] max = new long[k + 1][n + 1];//max[k][n]表示到n为止k个学生的最大乘积
long[][] min = new long[k + 1][n + 1];long multi = Integer.MIN_VALUE;
for (int i = 1;i <= n;i ++){ max[1][i] = ability[i]; min[1][i] = ability[i]; for (int j = 2;j <= k;j ++){ for (int pre = i - 1;pre > 0 && i - pre <= d;pre --){ max[j][i] = Math.max(max[j][i],Math.max(max[j - 1][pre] * ability[i],min[j - 1][pre] * ability[i])); min[j][i] = Math.min(min[j][i],Math.min(max[j - 1][pre] * ability[i],min[j - 1][pre] * ability[i])); } } multi = Math.max(multi,max[k][i]);//重点！！ } System.out.println(multi); } } }