乘积和最大

发表于

题目

有 n 个学生站成一排，每个学生有一个能力值，想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？

输入描述

每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。

输出描述

输出一行表示最大的乘积。

例子

3

7 4 7

2 50

输出

49

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
n = int(raw_input().strip())

line = raw_input().strip().split(' ')

line2 = raw_input().strip()
arr = []
for l in line:
    arr.append(int(l))

getnum = int(line2.split(' ')[0])
maxspace = int(line2.split(' ')[1])


maxresult = 0

fmax = [[0 for col in xrange(n+1)] for row in xrange(getnum + 1)]
fmin = [[0 for col in xrange(n+1)] for row in xrange(getnum + 1)]
# print getnum
# print n
# print fmax
res = 0
for i in xrange(1, n+1):
    fmax[1][i] = arr[i-1]
    fmin[1][i] = arr[i-1]

    for k in xrange(2,getnum+1):
        j = i-1
        while True:
            if j > 0 and i-j <= maxspace:
                print fmax[k][i]
                print fmax[k - 1][j] * arr[i - 1]
                print fmin[k - 1][j] * arr[i - 1]

                fmax[k][i] = max(fmax[k][i], max(fmax[k - 1][j] * arr[i - 1], fmin[k - 1][j] * arr[i - 1]))
                fmin[k][i] = min(fmax[k][i], min(fmax[k - 1][j] * arr[i - 1], fmin[k - 1][j] * arr[i - 1]))
                j -= 1
            else:
                break
    res = max(res, fmax[getnum][i])

print res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Scanner;

public class PuductMax {
        public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNextInt()) {
            int n = cin.nextInt();          // n 个学生
            int[] arr = new int [n+1];
            for (int i = 1; i <=n ; i++) {
                arr[i] = cin.nextInt();
            }
            int K = cin.nextInt();            // 选出K个
            int d = cin.nextInt();            // 两个学生的位置编号的差不超过 d
            long[][] fmax = new long[K+1][n+1]; // 记录最大乘积
            long[][] fmin = new long[K+1][n+1]; // 记录最小乘积
            // fmax[k][i]表示 : 当选中了k个学生，并且以第i个学生为结尾，所产生的最大乘积；
            // fmin[k][i]表示 : 当选中了k个学生，并且以第i个学生为结尾，所产生的最小乘积；
            //初始化第一行
            long  res = Integer.MIN_VALUE; // 记得用Long类型，考虑数值范围
            for (int i = 1; i <=n; i++) {
                fmax[1][i] = arr[i];
                fmin[1][i] = arr[i];
                for (int k = 2; k <=K; k++) {
                    for (int j = i-1 ; j > 0 &&  i-j<=d ; j--) {
                        fmax[k][i] = Math.max(fmax[k][i], Math.max(fmax[k-1][j] * arr[i], fmin[k-1][j] * arr[i]));
                        fmin[k][i] = Math.min(fmin[k][i], Math.min(fmax[k-1][j] * arr[i], fmin[k-1][j] * arr[i]));
                    }
                }
                res = Math.max(res ,fmax[K][i]);
            }
            System.out.println(res);
            break;
        }
    }
}