<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:
        #use sliding window + prefix sum to get the windows that = target
        # for any start position we want the rightmost end position
        # Now the question I had was if we always wanted to greedily take earliest window. answer is yea
        # Ex. thing of merge intervals + we want to have our previous interval have the earliest start to max the amount of intervals we can add
        ends = {} #start: end 

        subarray_sums = {0:-1} # prefix_sum: end
        contig_sum = 0
        last_end = -1
        res = 0
        for r in range(len(nums)):
            contig_sum += nums[r]

            comp = contig_sum - target #contig_sum - prev_section = target

            if comp in subarray_sums: # always want the earliest end for each start
                start = subarray_sums[comp]+1
                if start not in ends:
                    ends[start] = r
                    if last_end < start:
                        res +=1
                        last_end = r

            subarray_sums[contig_sum] = r
        return res


        # #now with our overlapping subarrays we run a dp

        # def get_non_overlapping(i):
        #     if i == len(nums):
        #         return 0

        #     if i in cache:
        #         return cache[i]
            
        #     non_overlapping = get_non_overlapping(i+1) #skip over index

        #     if i in ends:
        #         non_overlapping = max(non_overlapping, 1 + get_non_overlapping(ends[i]+1) )
            
        #     cache[i] = non_overlapping
        #     return non_overlapping

        # cache = {}
        # return get_non_overlapping(0)
            

35100