网易编程题 合唱团

题目描述 有 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

n = int(input())

nums = list(map(int, input().split()))

k, d = map(int, input().split())

# maxVal[i][j]以第i人为结尾，一共选了j个人的最大乘积

# minVal[i][j]以第i人为结尾，一共选了j个人的最小乘积

maxVal = [[1 for _ in range(k+1)] for _ in range(n+1)]

minVal = [[1 for _ in range(k+1)] for _ in range(n+1)]

max_value = 0

for i in range(1, n+1):

    for j in range(1, min(k+1, i+1)):

        for t in range(max(0, i-d), i):

            maxVal[i][j] = max(maxVal[i][j], maxVal[t][j-1] * nums[i-1], minVal[t][j-1] * nums[i-1])

            minVal[i][j] = min(minVal[i][j], minVal[t][j-1] * nums[i-1], maxVal[t][j-1] * nums[i-1])

    max_value = max(max_value, maxVal[i][k])

print(max_value)