有 n 个学生站成一排,每个学生有一个能力值,牛牛想从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能力值的乘积最大,你能返回最大的乘积吗?
输出一行表示最大的乘积.
给出 n 个数字,要求按顺序选择 k 个,使得选出的数的乘积最大.且要求选择的相邻两个人的距离必须小于等于 d.
但是这里面包含负数,所以我们要把 dp 拆成两个来定义:
现在的问题是,我们知道当前选择的第 k 个人是位置为 n 的人,那么选择的第 k-1 个人的位置在哪里?
首先有,第 k-1 个人的位置一定>=k-1(如果从1开始每一个都选,那么它只能到k-1)
我们看一下题目上的约束条件,要求选择的两个人相邻的距离必须小于等于 d ,那么他的位置一定 >=n-d因为必须小于等于 d.
且 他的位置一定是小于等于 n-1 的.
所以假设我们要算的第 k-1 个人的位置为 l 那么满足 max(k-1n-d)<=l<=n-1.
因为数里面有负数,所以我们dp的时候,