<p>Given an array <code>nums</code> and an integer <code>target</code>, return <em>the maximum number of <strong>non-empty</strong> <strong>non-overlapping</strong> subarrays such that the sum of values in each subarray is equal to</em> <code>target</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1,1,1], target = 2
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are 2 non-overlapping subarrays [<strong>1,1</strong>,1,<strong>1,1</strong>] with sum equals to target(2).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1,3,5,1,4,2,-9], target = 6
<strong>Output:</strong> 2
<strong>Explanation:</strong> There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= target &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        '''
        Initial thought: Keep two pointers and if the sum is equal to target, increase the count and set p1,p2 to p2+1
        If sum > target: increase p1, reduce s by nums[p1]
        And if sum < target: increase p2, increase s by nums[p2]

        Why that won't work: Take an example [3,4,-1,4,3,1], target = 6 now p1 = 0 and p2 = 1, sum = 7 Now we incr p1, which isn't right
        We would never be able to find [3,4,-1] like that

        Another approach: Store the prefix sums and remember which is the last used index
        for each number, we see if a subarray starting from last_used +1 or later can have a sum == target
        If so
        '''
        ps = {}
        ps[0] = -1
        last_used = -2#We have't used anything. -2 so that we get to inclde p[0]
        s = 0
        ans = 0
        for i in range(len(nums)):
            # Prefix sum till ith num
            s += nums[i]
            #We want a subarray with prefix sum rem
            rem = s-target
            # We have a sub array after last_used index
            if rem in ps and ps[rem] >= last_used:
                ans += 1
                last_used = i
            ps[s] = i
        return ans
35400