牛客网2017年校招真题-1

# 获取输入
n = int(input())
arr = map(int, input().split())
K, D = map(int, input().split())

# fm[k][i]表示当选中了k个学生，并且以第i个学生为结尾，所产生的最大乘积；
fm = [([0] * n) for i in range(K)]  # k*d

#  fn[k][i]表示 当选中了k个学生，并且以第i个学生为结尾，所产生的最小乘积；
fn = [([0] * n) for i in range(K)]  # k*d
res = 0

for i in range(n):
    fm[0][i] = arr[i]
    fn[0][i] = arr[i]

    """
定义fm[k][i]表示当选中了k个学生，并且以第i个学生为结尾，所产生的最大乘积；
        fn[k][i]表示 当选中了k个学生，并且以第i个学生为结尾，所产生的最小乘积；
那么fm[k+1][i+1]=max(fm[k][i]*stu[i+1],fn[k][i]*stu[i+1])，
        即当选中了k个学生后，再选择第i+1编号学生，所产生的最大乘积；
        然而，并不能保证上一次选择的就是第i个学生，所以要遍历子数组fm[k]，
        令j从i到1，并且j与i+1之间小于间隔D，遍历fm[k][j]，以及fn[k][j]；
同理fn[k+1][i+1]=min(fn[k][i]*stu[i+1],fm[k][i]*stu[i+1])。
最后，遍历一遍fm[K][i]求得最大值（i从1～N）。
    """

for i in range(n):
    for k in range(1, K):
        # for j in range(i-1,-1,-1):
        for j in range(i - 1, max(0, i - D) - 1, -1):
            # if (i-j<D and k>0):
            fm[k][i] = max(fm[k][i], max(fm[k - 1][j] * arr[i], fn[k - 1][j] * arr[i]))
            fn[k][i] = min(fn[k][i], min(fm[k - 1][j] * arr[i], fn[k - 1][j] * arr[i]))

    res = max(res, fm[K - 1][i])

print(res)