网易2018编程题_求能力值的最大乘积

我不是女神ヾ 2022-06-07 02:35 281阅读 0赞

> 题目：有 n 个学生站成一排，每个学生有一个能力值，想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
> 
> 输入：  
> 第一行：一个整数 n (1 <= n <= 50)，表示学生的个数  
> 第二行： n 个整数，按顺序表示每个学生的能力值 ai（-50<= ai<=50）  
> 第三行：两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)
> 
> 输出：  
> 最大乘积

这是一个动态规划问题。

**从n个学生中选择k个**可以看成：  
**先从n个学生里选择最后1个，然后在剩下的里选择k-1个，并且让这1个和前k-1个满足约束条件。**

> last表示第k个人位置，范围\[1,n\]  
> left表示第k-1个人的位置\[max\{k-1,last-d\} , last-1\]  
> f\[last\]\[k\]表示从n个人中选择k个的最大乘积。  
> f\[left\]\[k-1\]表示从k前面的left个人中选择k-1个的最大乘积。  
> ai\[i\]表示第i个学生的能力值

因为能力值有正有负，所以如果能力值为负，乘以前面求得的最小负积，结果才是最大乘积。  
f\[\]\[\]是存储n个选k个能力值乘积的最大值的数组。  
g\[\]\[\]是存储n个选k个能力值乘积的最小值的数组。

> last对应的学生，也就是第k个人能力值为正时：  
> f\[last\]\[k\] = max\{ f\[left\]\[k-1\] , arr\[i\] \}，left范围是\[max\{k-1,last-d\} ,last-1\]
> 
> last对应的学生，也就是第k个人能力值为负时：  
> f\[last\]\[k\] = min\{ g\[left\]\[k-1\] , arr\[i\] \}，left范围是\[max\{k-1,last-d\} ,last-1\]

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class Solution{
        
        public static void main(String[] args) throws IOException {
            BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(bf.readLine());
            int[] ai = new int[n+1];
    
            String[] num2 = bf.readLine().split(" ");
            for(int i = 1;i <= n;i++)
                //ai[i]表示学生的能力值
                ai[i] = Integer.parseInt(num2[i-1]);
    
            String[] num3 = bf.readLine().split(" ");
            int k = Integer.parseInt(num3[0]);//选取k个学生
            int d = Integer.parseInt(num3[1]);//编号之差不超过d
    
            //求最大乘积的时候，每一步需要求最大正积和最小负积
            //因为如果某学生的能力值为负数，乘以前面求得的最小负积，结果才是最大乘积
            //最后算的数据比较大，需要用long
            // max[k][h]表示 : 当选中了h个学生，并且以第k个学生为结尾，所产生的最大乘积；
            // min[k][h]表示 : 当选中了h个学生，并且以第k个学生为结尾，所产生的最小乘积；
            long[][] max =  new long[n+1][k+1];
            long[][] min =  new long[n+1][k+1];
            long res = Integer.MIN_VALUE;
            for(int last = 1;last<= n;last++){
                //初始化h=1的情况，只选中1个人的情况
                max[last][1] = ai[last];
                min[last][1] = ai[last];
                //h>1的情况，选中人数从2开始
                for(int h = 2;h <= k;h++){
                    for(int left = last-1; left>0 && last-left<=d;left--){
                        max[last][h] = Math.max(max[last][h],Math.max(max[left][h-1]*ai[last],min[left][h-1]*ai[last]));
                        min[last][h] = Math.min(min[last][h],Math.min(max[left][h-1]*ai[last],min[left][h-1]*ai[last]));
                    }
                }
                res = Math.max(res, max[last][k]);
            }
            System.out.println(res);        
        }   
    }

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220607/03d0ef285a2344b8a18d8b0ac28e7856.png