题解 | #最大数#

题目描述
给定一些人，每个人有一个聪明值Si(-1000<=Si<=1000)和勤奋值Fi(-1000<=Fi<=1000).
希望选入所有人的Si+Fi的总和最大，并且选中的人的聪明值与勤奋值的和不能是负数
给出每个同学分别的聪明值和勤奋值，求出最大的总和。

返回一个vector代表对这q个询问的答案

方法一：暴力求解

求解思路
对于本题目的求解，我们可以采用暴力的方法进行求解，对于选择同学作为同事，我们可以想到每位同学都会有两种状态，选或者不选。因此我们基于上面的思路，我们可以设置一个数组来记录所有的聪明值和勤奋值的累加情况。对于数组我们对其进行排序，并且维护一个递增的顺序，然后最后将最大的组合找出来，然后过滤掉题目中“个人聪明值与勤奋值的和不能是负数”的情况，最后即可得到本题的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int smartSum (int number, int[] si, int[] fi) {
        List<int[]> mylist=new ArrayList<>();
        mylist.add(new int[]{0,0});
        for(int i = 0;i < number;i ++)
        {
            int num=mylist.size();
            for(int j=0;j<num;j++)
            {
                mylist.add(new int[]{mylist.get(j)[0]+si[i],mylist.get(j)[1]+fi[i]}); // 更新“维护列表”
            }
            Collections.sort(mylist,(o1,o2)->o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0]); // 排序
            List<int[]> mystack=new ArrayList<>();
            for(int[] sum:mylist)
            {
                while(!mystack.isEmpty()&&mystack.get(mystack.size()-1)[1]<=sum[1])
                {
                    mystack.remove(mystack.size()-1); // 更新“维护栈”
                }
                mystack.add(sum); // 添加元素
            }
            mylist=mystack; // 赋值即可
        }
        int myres=0; // 存储最后结果
        for(int[] sum:mylist)
        {
            if(sum[0]>0&&sum[1]>0)
            {
                myres=Math.max(myres,sum[0]+sum[1]);
            }
        }
        return myres;
    }
}

复杂度分析
时间复杂度：指数式循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用额外的内存地址空间存储mylist，因此空间复杂度为 $O$ ( $图片说明$ )

方法二：动态规划思想求解

求解思路
对于本题我们也可以使用动态规划的思想进行求解，我们可以将聪明值看作背包容量，勤奋值看作要装入背包物品的价值，因此根据上述思路我们也可得到本题的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    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; // 背包问题中的容量
        int[] mydp=new int[capacity+1];
        Arrays.fill(mydp,Integer.MIN_VALUE);
        mydp[-min]=0; // 特殊情况赋值
        for(int i=0;i<number;i++)
        {
            if(si[i]>0) // 大于0的情况的处理
            {
                for(int j=capacity;j>=si[i];j--)
                {
                    if(mydp[j-si[i]]!=Integer.MIN_VALUE)
                    {
                        mydp[j]=Math.max(mydp[j],mydp[j-si[i]]+fi[i]); // 维护最大值
                    }
                }
            }
            else
            {   //小于0的情况的处理
                for(int j=0;j<=capacity+si[i];j++)
                {
                    if(mydp[j-si[i]]!=Integer.MIN_VALUE)
                    {
                        mydp[j]=Math.max(mydp[j],mydp[j-si[i]]+fi[i]); // 维护最大值
                    }
                }
            }
        }
        int myres=0;
        for(int i=-min+1;i<=capacity;i++)
        {
            if(mydp[i]>0)
            {
                myres=Math.max(myres,mydp[i]+i+min);
            }
        }
        return myres; // 返回结果
    }
}

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用mydp[N]数组，使用额外的内存地址空间，因此空间复杂度为 $O(N)$