题目：

  1. 给你一个数组 nums 和一个整数 target 。
  3. 请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。
  5. 示例 1：
  7. 输入：nums = [1,1,1,1,1], target = 2
  8. 输出：2
  9. 解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。
  10. 示例 2：
  12. 输入：nums = [-1,3,5,1,4,2,-9], target = 6
  13. 输出：2
  14. 解释：总共有 3 个子数组和为 6 。
  15. ([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。
  16. 示例 3：
  18. 输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10
  19. 输出：3
  21. 来源：力扣（LeetCode）
  22. 链接：https://leetcode-cn.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target
  23. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

10 min

  1. class Solution:
  2.     def maxNonOverlapping(self, nums: List[int], target: int) -> int:
  3.         n=len(nums)
  4.         dp=[0]*(n+1)
  5.         prefix=[0]
  6.         for num in nums:
  7.             prefix.append(prefix[-1]+num)
  8.         record={prefix[0]:0}
  10.         for i in range(1,n+1):
  11.             dp[i]=max(dp[i],dp[i-1])
  12.             val= prefix[i]-target
  13.             if val in record:
  14.                 pos=record[val]
  15.                 dp[i]=max(dp[i],dp[pos]+1)
  16.             record[prefix[i]]=i
  17.         return dp[-1]

要点：

1. dp 定义：前i个能拆几段

2. 转移方程：

if sum[i:j]=target: dp[i]=max(dp[i],dp[pos]+1)
这里的sum[i:j] 用前缀和表示，这里的pos 是离j最近的一个i（贪心）

3. 更新点

这一个一定比上一个大，dp[i]=max(dp[i],dp[i-1])
更新记录的前缀和，来锁定离 j 最近的 i ，所以是时时更新。

其他：

代码报错：无