本文共 1375 字，大约阅读时间需要 4 分钟。

题目描述 

有 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

解题参考： 

解题思路及代码：  原理类似于迭代求解函数，考虑k=1作为初始点，来推断k=2时的结果，其中需要注意负负得正。

# f [ i ] [ j ] [ 0 / 1 ]表示，总人数为j，以第i个人为最后一个人，乘积的最大值和最小值。# 考虑到负负得正，所以需要保留负数中的最小值。# 通过公式f[i][j]=max(fm[k][j-1]*stu[j],fn[k][j-1]*stu[j])，可以一次遍历得出结果n = int(input())# 与版本2不同，python3中，map函数返回一个map对象，而不是list，需要转换；# http://www.cnblogs.com/GatsbyNewton/p/4784049.htmlarray = list(map(int,input().split()))k,d = map(int,input().split())# 初始化三维数组（大小），由内到外resArray = [[[0] * 2 for j in range(k+1)] for i in range(n)]result = 0;# i表示最后一个数位于array数组位置下标i处，j表示当前乘积的数字个数，0、1分别记录最大值和最小值# 遍历个数和位置for i in range(0,n):    # 当乘积个数为1时，结果为当前这个数。    resArray[i][1][0],resArray[i][1][1]=array[i],array[i]    for j in range(2,k+1):        # 考虑间隔d        for m in range(max(i-d,0),i):            resArray[i][j][0] = max(resArray[i][j][0]                ,max(resArray[m][j-1][0]*array[i],resArray[m][j-1][1]*array[i]))            resArray[i][j][1] = min(resArray[i][j][1]                ,min(resArray[m][j-1][0]*array[i],resArray[m][j-1][1]*array[i]))    result = max(result,max(resArray[i][k][0],resArray[i][k][0]))print(result)