题解 | #牛妹的招聘#

题意整理

• 有n个同学，每个同学都有一个聪明值和一个勤奋值。
• 从这个n个同学中选出若干同学，使得总的聪明值累加和和勤奋值累加和最大，但是聪明值累加和、勤奋值累加和必须大于0。

方法一（单调栈）

1.解题思路

• 牛妹想选择一些同学作为同事，如果最终有N个同学，那么总的组合数就是 （每个同学，要么选，要么不选）。同学数限定小于100，直接暴力递归进行搜索，最多有 次，肯定会超时。所以在每次选择时，要找出淘汰策略。
• 我们用一个list记录所有可能的聪明值累加和与勤奋值累加和，假设当前累加和组合数为n，每新增一位同学，就多出n种组合，如果能提前淘汰不可能是最大总和的组合，就会减少很多无用搜索。当我们得到这 种组合后，首先按聪明值累加和进行排序，如果聪明值累加和相等，按勤奋值累加和排序（可以淘汰聪明值累加和相等，勤奋值累加和递增的情况）。然后维护一个单调栈，遍历list中的组合，由于是按聪明值从小到大排序，所以当前组合聪明值累加和总是比栈顶的聪明值累加和大，如果勤奋值也不小于栈顶的，那栈顶组合肯定不会是最大总和，可以排除。遍历完之后，再将list替换为单调栈。
• 当所有可能最大的组合找出来之后，再过滤掉单个累加和小于等于0的情况，在list中找最大总和即可。

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 参加校招的同学人数
     * @param si int整型一维数组 这个同学的聪明值
     * @param fi int整型一维数组 这个同学的勤奋值
     * @return int整型
     */
    public int smartSum (int number, int[] si, int[] fi) {
        //创建一个list用于存储聪明值和勤奋值累加和
        List<int[]> list=new ArrayList<>();
        list.add(new int[]{0,0});

        for(int i = 0;i < number;i ++){
            //相当于对list进行层序遍历,让每一个累加和与当前同学的聪明值、勤奋值组合，扩展出更多的可能
            int n=list.size();
            for(int j=0;j<n;j++){
                list.add(new int[]{list.get(j)[0]+si[i],list.get(j)[1]+fi[i]});
            }
            //按聪明值累加和进行排序，如果相等，按勤奋值累加和排序
            Collections.sort(list,(o1,o2)->o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]);

            //维护一个单调栈，使得聪明值累加和递增的情况下，勤奋值累加和递减
            List<int[]> stack=new ArrayList<>();
            for(int[] sum:list){
                //如果聪明值累加和小于当前，勤奋值累加和也不大于当前，直接将栈顶元素移除
                while(!stack.isEmpty()&&stack.get(stack.size()-1)[1]<=sum[1]){
                    stack.remove(stack.size()-1);
                }
                stack.add(sum);
            }

            //将list替换为清除无效组合后的集合
            list=stack;
        }
        int res=0;
        //找到最大的总和
        for(int[] sum:list){
            if(sum[0]>0&&sum[1]>0){
                res=Math.max(res,sum[0]+sum[1]);
            }
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：组合数会呈指数式增长，形如 的样子扩张，最坏情况下，没有淘汰任何组合，总组合数为（n是应聘的同学数），所以时间复杂度是 。
• 空间复杂度：最坏情况下，需要额外大小为的list，所以空间复杂度为 。

方法二（动态规划）

1.解题思路

问题可以转化为一个01背包问题，以聪明值累加和为容量，以勤奋值累加和为价值，在不超过最大容量的前提下，求最大的价值。首先要确定背包的容量，先求聪明值累加和的最小值和最大值，由于dp数组以0开始，所以容量偏移 个单位。

• 状态定义： 表示聪明值累加和为 时，勤奋值累加和的最大值。
• 状态初始化：将所有的状态初始化为int型数据最小值，并将聪明值累加和为0时的勤奋值累加和赋为0。
• 状态转移：由于是01背包问题，需要从后往前推算出状态，如果从前往后，会将之前的状态多算。然后，每多一个 ，就多一个 ，即 ； 时, 相较于j要大，是从大的聪明值累加和转化到小的聪明值累加和，根据01背包，应该倒过来从前往后推，左边界是dp数组左边界0，右边界为了 不超过capacity，所以是 ，状态转移方程也是 。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 参加校招的同学人数
     * @param si int整型一维数组 这个同学的聪明值
     * @param fi int整型一维数组 这个同学的勤奋值
     * @return int整型
     */
    public int smartSum (int number, int[] si, int[] fi) {
        //计算聪明值累加和的最小值和最大值
        int min=0,max=0;
        for(int i=0;i<number;i++){
            if(si[i]<0){
                min+=si[i];
            }
            else{
                max+=si[i];
            }
        }

        int capacity=max-min;
        //dp[i]表示聪明值累加和为i+min时，勤奋值累加和的最大值
        int[] dp=new int[capacity+1];
        Arrays.fill(dp,Integer.MIN_VALUE);
        //初始化聪明值累加和为0的情况
        dp[-min]=0;
        for(int i=0;i<number;i++){
            if(si[i]>0){
                //01背包问题，聪明值累加和一定，选最大勤奋值累加和
                for(int j=capacity;j>=si[i];j--){
                    if(dp[j-si[i]]!=Integer.MIN_VALUE){
                        dp[j]=Math.max(dp[j],dp[j-si[i]]+fi[i]);
                    }
                }
            }
            else{
                //如果是负数，需要从之前确定的聪明值累加和倒推
                for(int j=0;j<=capacity+si[i];j++){
                    if(dp[j-si[i]]!=Integer.MIN_VALUE){
                        dp[j]=Math.max(dp[j],dp[j-si[i]]+fi[i]);
                    }
                }
            }
        }

        int res=0;
        //如果聪明值累加和大于0，同时勤奋值累加和大于0，取两者之和最大值
        for(int i=-min+1;i<=capacity;i++){
            if(dp[i]>0){
                //i+min表示聪明值累加和
                res=Math.max(res,dp[i]+i+min);
            }
        }
        return res;

    }
}

3.复杂度分析

• 时间复杂度：第一层循环n次（n是应聘的同学数），第二层循环最多有capacity+1次（capacity是聪明值累加和最大值与最小值之差），所以时间复杂度是 。
• 空间复杂度：需要额外大小为capacity+1的dp数组，所以空间复杂度为 。