<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:
        # fix subarray [j, i] that sum = target
        # f[i]: maximum # subarrays that sum of values in subarrays = target, ending at i
        # f[i] = f[i - 1]
        # f[i] = f[j - 1] + 1, if sum[j, i] = target for all 1 <= j <= i
        # f[i] = max(f[j - 1]) + 1, if ps[i] - target = ps[j - 1] 

        prefix_sum = [0 for i in range(len(nums) + 1)]
        for i in range(1, len(nums) + 1):
            prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]

        f = [0 for i in range(len(nums) + 1)]
        max_f = {0: 0}
        for i in range(1, len(nums) + 1):
            f[i] = max(f[i], f[i - 1])

            # sum = 0
            # for j in range(i, 0, -1):
            #     sum += nums[j - 1]
            #     if sum == target:
            #         f[i] = max(f[i], f[j - 1] + 1)

            prefix_j = prefix_sum[i] - target
            if prefix_j in max_f:
                f[i] = max(f[i], max_f[prefix_j] + 1)
            max_f[prefix_sum[i]] = f[i]

        return f[len(nums)]
                



34300