编程题：合唱团

╰半夏微凉° 2022-05-24 12:14 70阅读 0赞

## 题目描述 ##

有 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

## 输出 ##

复制

### 解题思路： ###

元素有正有负，要考虑负负得正的情况

相邻元素间隔不超过d

使用**动态规划**，从最后一个元素入手

为了理解方便，我们将行数为0和列数为0的元素都赋值为0不去考虑，可以看作下标从1开始

代码实现：

package net.stxy.one.controller;
    
    import java.util.Scanner;
    
    /**
     * Created by ASUS on 2018/5/26
     *
     * @Authod Grey Wolf
     */
    public class Test1 {
    
        public static void main(String[] args) {
            Test1 test = new Test1();
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int[] m = new int[n + 1];
            int i;
            for (i = 1; i < n + 1; i++) {
                m[i] = scanner.nextInt();
            }
            //选取k个学生
            int k = scanner.nextInt();
            //相邻2个学生的差距值
            int d = scanner.nextInt();
            //返回的最大值
            int sum = test.getResult(n, m, k, d);
            System.out.println("sum:" + sum);
        }
    
        private int getResult(int n, int[] m, int k, int d) {
            int maxResult = Integer.MIN_VALUE;
            // maxArr[k][i]表示 : 当选中了k个学生，并且以第i个学生为结尾，所产生的最大乘积；
            int maxArr[][] = new int[k + 1][n + 1];
            // minArr[k][i]表示 : 当选中了k个学生，并且以第i个学生为结尾，所产生的最小乘积；
            int minArr[][] = new int[k + 1][n + 1];
            int i, j, stuNum;
            for (i = 1; i <= n; i++) {
                //第k个人i结束,初始化选取一个学生
                maxArr[1][i] = m[i];
                minArr[1][i] = m[i];
                //选取k个学生
                for (stuNum = 2; stuNum <= k; stuNum++) {
                    //表示从前j个中选出j-1个最大的乘积，所以i-j<d只能最多回溯d个或者回溯到底
                    for (j = i - 1; j > 0 && i - j < d; j--) {
                        //选择下一个学生的时候，有可能是负数乘以最小的值变成了最大的数。因为负负得正。
                        maxArr[stuNum][i] = Math.max(maxArr[stuNum][i], Math.max(maxArr[stuNum - 1][j] * m[i], minArr[stuNum - 1][j] * m[i]));
                        minArr[stuNum][i] = Math.min(maxArr[stuNum][i], Math.min(maxArr[stuNum - 1][j] * m[i], minArr[stuNum - 1][j] * m[i]));
                    }
                }
                maxResult = Math.max(maxArr[k][i], maxResult);
            }
            return maxResult;
        }
    }

输出效果：

3  
7 4 7  
2 50  
sum:49  
  
Process finished with exit code 0

我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。