题意

给两个等长的数组。

选择一系列坐标，使得两个数组对应位置分别的和非负，且对应位置的值总和最大。求这个最大值。

范围：数组长度最大100，数值绝对值<1000

样例有误 应该是11

方法

dfs(TLE)

我们通过深搜，遍历每一个人选择或者不选择。遍历到最后一个人时，统计是否满足非负，同时返回和。

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param number int整型 参加校招的同学人数
# @param si int整型一维数组 这个同学的聪明值
# @param fi int整型一维数组 这个同学的勤奋值
# @return int整型
#
class Solution:
    # idx 当前递归的下标 有效范围是0 ~ number-1
    # scount 选择了的 si的总和
    # fcount 选择了的 fi的总和
    def dfs(self, number,si,fi,idx,scount,fcount):
        if idx == number: # 有效范围选或不选完厚的边界
            if scount >= 0 and fcount >= 0:
                return scount + fcount
            return 0
        return max(
            self.dfs(number,si,fi,idx+1,scount,fcount), # 不选择下标为idx的
            self.dfs(number,si,fi,idx+1,scount+si[idx],fcount+fi[idx]), # 选择下标为idx的
        )
            
    def smartSum(self , number , si , fi ):
        return self.dfs(number,si,fi,0,0,0)

复杂度分析

时间复杂度: 我们尝试了每一个人的选和不选，因此时间复杂度为$O\left(2^n\right)O(2^n)$O(2n)

空间复杂度: 攻坚主要在递归上消耗，复杂度与递归深度相关，递归深度最大为数组长度所以，空间复杂度为$O\left(n\right)O(n)$O(n)

动态规划

题目的目标是，都非负。

那么我们把人看成4种

对于上面需要再讨论的（也就是一正一负的），我们还可以直接淘汰一些和为负的吗？

并不是，例如：

如果目前有$(1,1),(-2,1000),(1,-2)(1,1),(-2,1000),(1,-2)$(1,1),(−2,1000),(1,−2)

首先我们知道$(1,1)(1,1)$(1,1)一定会选

然而对于$(1,-2)(1,-2)$(1,−2) 虽然它总贡献是负数，但实际上如果没有它，第二个是无法被选择的。

因此 对于一些和为负数，但是一半正，一半负的并不能直接淘汰。

换一个角度，假设已经完成了选择，那么没有被选的一定两两之和小于等于0或者有一项为负，否则把这两个同时选入，则答案会更优。

由此，无法完成局部最优

虽然这里的s和f看上去是同样层级的值，但是我们从数学意义上，可以看成求不同的s的和所对应的f的和的最大值，再在这些和为正的里面找f为正的进行相加。

需要注意的是，s可能正，可能负，所以状态转移时记得控制遍历顺序，保证f仅转移了一次

例如 当前假设有，那么如果$s=1s\; =\; 1$s=1,如果遍历顺序从小到大，会让4和5都合法，而实际上只能转移一次，只能让4合法，所以要从大到小遍历。如果$s=-1s=-1$s=−1，如果从大到小遍历，则会让1和2都合法，而实际上只能让2合法，所以要从小到大遍历

综上，如果s为正，反向遍历，s为负正向遍历。s为0，f为正，所有合法值增加f。

最后答案为遍历一遍所有正s，且最大f为正f，求其中的最大和。

转移方程:

$s_i>0,dp\left[count\right]=max\left(dp\right[count],dp[count-s_i]+f_i)s\_i\; >\; 0,\; dp[count]\; =\; max(dp[count],dp[count\; -\; s\_i]\; +\; f\_i)$si​>0,dp[count]=max(dp[count],dp[count−si​]+fi​),其中$countcount$count从大到小转移

si​<0,dp[count]=max(dp[count],dp[count−si​]+fi​),其中$countcount$count从小到大转移

$s_i=0,dp\left[count\right]=max\left(dp\right[count],dp[count]+f_i)s\_i\; =\; 0,\; dp[count]\; =\; max(dp[count],dp[count]\; +\; f\_i)$si​=0,dp[count]=max(dp[count],dp[count]+fi​)

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param number int整型 参加校招的同学人数
     * @param si int整型vector 这个同学的聪明值
     * @param fi int整型vector 这个同学的勤奋值
     * @return int整型
     */
    int smartSum(int number, vector<int>& si, vector<int>& fi) {
        const int INF = 0x3f3f3f3f;
        const int OFFSET = 1000*100;
        const int MAXS = 2000*100;
        vector<int> dp(MAXS+1,-INF); // dp[s的和] = 能达到的最大的f的和
        dp[OFFSET] = 0;
        for(int i = 0;i<si.size();i++){
            if(si[i] > 0){ // 对于大于零的
                for(int j = MAXS;j>=0;j--){ // 从大到小转移
                    if(dp[j] == -INF)continue;
                    if(j+si[i] > MAXS)continue;
                    dp[j+si[i]] = max(dp[j+si[i]],dp[j]+fi[i]);
                }
            }else if(si[i] < 0){ // 对于小于零的
                for(int j = 0;j<=MAXS;j++){ // 从小到大转移
                    if(dp[j] == -INF)continue;
                    if(j+si[i] < 0)continue;
                    dp[j+si[i]] = max(dp[j+si[i]],dp[j]+fi[i]);
                }
            }else if(fi[i] > 0){ // si[i] == 0 等于零的
                for(int j = MAXS;j>=0;j--){
                    if(dp[j] == -INF)continue;
                    dp[j] += fi[i]; // 自增
                }
            }
        }
        int ans = 0;
        for(int i = OFFSET;i<=MAXS;i++){ // s 的和 非负的范围内找
            if(dp[i] < 0)continue;
            ans = max(ans,i+dp[i]-OFFSET);// 最大的 s的和 加 f的和
        }
        return ans;
    }
};

复杂度分析

空间复杂度: 我们的状态设计是 总s对应最大的f，所以状态数与s的值范围有关,所以最大为$O(s_{max}-s_{min})O(s\_\{max\}-s\_\{min\})$O(smax​−smin​)

时间复杂度: 时间复杂度为下标乘状态乘转移代价，转移代价为常数，所以时间复杂度是$O(n\cdot (s_{max}-s_{min}\left)\right)O(n\backslash cdot\; (s\_\{max\}-s\_\{min\}))$O(n⋅(smax​−smin​))