题目要求
有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，
要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
题目解析
思路一：
- 分析
1、要找出n个同学里面的K个同学，而且使之能力值的乘积最大，我们可以看成先在n个同学中找到K个同学中的最后一个。
然后再在找到的同学的左边，找出K-1个同学。并使之符合约束。
2、首先我们可以假设他找到的最后一个下标为one，而从n个数中要取得k个数的方法就有f[k][one]中，那么left为one左边的第一个，那么
找到left的方法有f[k-1][left]种。那么有max{ k-1 , one - d} <= left <= n-1 }
3、既然n与k已经确定，接下来只需要对数据进行递推。
用两个二维数组存储当最后一个选中的值坐标为one需要选择的为k时，其最大最小值应该为kk[n][k] ; gg[n][k] ;
注意：要考虑正负数问题，区分当前one所在地址的值为正数还是复数。
- 代码段
public class Text {
public static void getResult() {
int n ;
int[] arr ;
int k ;
int d ;
Scanner sc = new Scanner(System.in) ;
while(sc.hasNext()) {
n = sc.nextInt() ;
arr = new int[n+1] ;
for(int i = 1 ; i <= n ; i++ ) {
arr[i] = sc.nextInt() ;
}
k = sc.nextInt() ;
d = sc.nextInt() ;
//存储最大值
long[][] aa = new long[k+1][n+1] ;
//存储最小值
long[][] ll = new long[k+1][n+1] ;
//将K = 1 的情况保存
for(int one = 1 ; one <= n ; one++) {
aa[1][one] = arr[one] ;
ll[1][one] = arr[one] ;
}
long maxtemp = 0 ;
long mintemp = 0;
//从底层递推
for(int kk = 2 ; kk <= k ; kk++ ) {
for(int one = kk ; one <= n ; one++) {
maxtemp = Long.MIN_VALUE ;
mintemp = Long.MAX_VALUE ;
//对one左边的进行检索，找出最大值和最小值
for(int left = one-1 ; left >= Math.max(kk-1, one-d) ; left-- ) {
if(maxtemp < Math.max(arr[one]*ll[kk-1][left], arr[one]*aa[kk-1][left])) {
maxtemp = Math.max(arr[one]*ll[kk-1][left], arr[one]*aa[kk-1][left]) ;
}
if(mintemp > Math.min(arr[one]*ll[kk-1][left], arr[one]*aa[kk-1][left])) {
mintemp = Math.min(arr[one]*ll[kk-1][left], arr[one]*aa[kk-1][left]) ;
}
}
aa[kk][one] = maxtemp ;
ll[kk][one] = mintemp ;
}
}
long result = Long.MIN_VALUE ;
for(int i = n ; i >= k ; i--) {
result = (result > aa[k][i]) ? result : aa[k][i] ;
}
System.out.println(result);
}
}
public static void main(String[] args) {
getResult();
}
}
输入用例
3
7 4 7
2 50
输出用例
49
感悟
这道题主要的点在我们是否能将要找出n个同学里面的K个同学，而且使之能力值的乘积最大，看成先在n个同学中找到K个同学中的最后一个。然后再在找到的同学的左边，找出K-1个同学。并使之符合约束。从而使用动态规划进行解析，得到结果。
（虽然很多人都知道，但总有人不知道，贴一下）
- 动态规划基本思想：
基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
