LeetCode 1546 和为目标值且不重叠的子数组的最大数目
🟠 中等偏上
思路
考虑到 i之前的大子数组的答案和 到 i-1 的大数组的答案，显然， nums[i] 的加入在 i-1 的答案 基础之上多了一种可能：有一个子数组在最右边包含了 nums[i] 。max( dp[i-1] ，1+dp[i-k] )
递归思路
或者递归思路：传入参数0，要么后移1位和当前区分开来，要么后移一个合法组数组。
fun(){
return max(fun(1),1+fun(k))
//0~k-1 是一个合法的子数组。
}
代码
for 循环中的 前缀和的更新在末尾，如果放在sum语句之后，[0,0,0] 这个用例会出错，因为本层后面还要用 hash_map ，提前更新导致错误，因此要放到最后。
class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int target) {
unordered_map<int,int> hash_map; // sum,i 包含arr[i-1]不包含 i。
hash_map[0] = 0;
int sum = 0;
vector<int> dp(nums.size()+1); //dp[i] 表示到i-1的答案
dp[0] = 0;
for(int i = 1;i<=nums.size();i++){
sum+=nums[i-1];
if(hash_map.count(sum-target)){
int index = hash_map[sum-target]-1;
dp[i] = max(dp[i-1],1+dp[1+index]);
}else{
dp[i] = dp[i-1];
}
hash_map[sum] = i;
}
return dp.back();
}
};