Given an array nums and an integer target.
Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.
 
Example 1:
Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).

Example 2:
Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: 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.
Example 3:
Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3

Example 4:
Input: nums = [0,0,0], target = 0
Output: 3

 
Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6

Difficulty: interview

Starter code:

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        

Solutions:
class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        sum_set = set()
        sum_set.add(0)
        temp = 0
        count = 0
        for num in nums:
            temp += num
            if temp - target in sum_set:
                count += 1
                sum_set.clear()
                sum_set.add(0)
                temp = 0
                continue
            sum_set.add(temp)
        return count



class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        res=0
        s=set()
        s.add(0)
        t=0
        for x in nums:
            t+=x
            if t-target in s:
                res+=1
                s.clear()
            s.add(t)
        return res


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        n = len(nums)
        cumsum = [0]*(n+1)

        for i in range(n):
            cumsum[i+1] = cumsum[i] + nums[i]

        d = {0:0}
        temp = []
        for i in range(n):
        #     print(i, cumsum[i+1]-target)
            if cumsum[i+1]-target in d:
                temp.append((d[cumsum[i+1]-target], i+1))
                # print(d[cumsum[i+1]-target], i+1)
            d[cumsum[i+1]] = i+1
        l = sorted(temp, key=lambda x:(x[0],x[1]))
        cur_s = -1
        cur_e = -1
        total = 0
        for s,e in l:
            if s >= cur_e:
                total += 1
                cur_s = s
                cur_e = e
            elif e < cur_e:
                cur_s = s
                cur_e = e
        return total

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        ans, m, j, cur = 0, {0:-1}, -1, 0            
        for i, x in enumerate(nums):
            cur += x
            k = cur - target            
            if k in m and m[k] >= j:
                ans += 1; j = i 
            m[cur] = i
        return ans
                    
                


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        dp = [0] * len(nums)
        prev_sum = {0: -1}
        
        num_nonover = 0
        current_sum = 0
        
        for (index, num) in enumerate(nums):
            current_sum += num
            
            if current_sum - target in prev_sum:
                gain = dp[prev_sum[current_sum-target]] if prev_sum[current_sum-target] >= 0 else 0
                
                num_nonover = max(num_nonover, gain + 1)
                
                
            dp[index] = num_nonover
            prev_sum[current_sum] = index
            
        return num_nonover
            
        


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        curSum = 0
        sumsSet = {0}
        result = 0
        for x in nums:
            curSum += x
            if (curSum - target) in sumsSet:
                result += 1
                curSum = 0
                sumsSet.clear()
            sumsSet.add(curSum)
            
        return result

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        
        dp = [0] * (n+1)
        
        dic = {}
        dic[0] = 0
        
        cur = 0
        
        for i in range(1, n+1):
            cur += nums[i-1]
            
            if cur - target in dic:
                dp[i] = 1 + dp[dic[cur - target]]
            
            dp[i] = max(dp[i-1], dp[i])
            
            dic[cur] = i
        
        return dp[n]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        d = {}
        d[0] = -1
        
        N = len(nums)
        
        if(N==0):
            return 0
        L = [0 for i in range(N)]
        s = nums[0]
        d[s] = 0
        if(s==target):
            L[0] = 1
        for i in range(1,N):
            s += nums[i]
            L[i] = L[i-1]
            if(s-target in d):
                idx = d[s-target]
                if(idx==-1):
                    L[i] = max(L[i],1)
                else:
                    L[i] = max(L[i],L[idx]+1)
            
            d[s] = i
        return L[N-1]


class Solution:
    def maxNonOverlapping(self, nums, target):
        ans = 0
        cur = 0
        tmp = set([0])
        for n in nums:
            cur += n
            if cur - target in tmp:
                ans += 1
                cur = 0
                tmp = set([0])
            tmp.add(cur)
        return ans

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        P = [0]
        for e in nums:
            P.append(P[-1]+e)
            
        seen = set()
        ans = 0
        
        for psum in P:
            if psum - target in seen:
                seen = {psum}
                ans += 1
            else:
                seen.add(psum)
                
        return ans

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        pre = [0]
        for n in nums:
            pre.append(pre[-1] + n)
        
        dp = {0: 0}
        counter = [0] * len(pre)
        
        for i in range(1, len(pre)):
            if pre[i] - target in dp:
                idx = dp[pre[i] - target]
                counter[i] = max(counter[i-1], counter[idx] + 1)
            else:
                counter[i] = counter[i-1]
            dp[pre[i]] = i
        return counter[-1]




class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:

        prefixsum = {}
        prefixsum[0] = True
        prev = 0
        res = 0
        for num in nums:
            curr = prev + num
            
            if curr - target in prefixsum:
                res += 1
                prefixsum = {}
                prefixsum[0] = True
                prev = 0
            
            else:
                prefixsum[curr] = True
                prev = curr
            
        print(res)
        return res
        
        
        
        
        






'''
class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        prefixsum = {}
        prefixsum[0] = 0
        res = 0
        last = -1
        prev = 0
        for idx, num in enumerate(nums):
            curr = prev + num
            prefixsum[curr] = idx
            
            if curr - target in prefixsum:
                if prefixsum[curr - target] >= last:
                    res += 1
                    last = prefixsum[curr]
            prev = curr 
        print(prefixsum)
        print(res)
        return res


'''


### good explanation in https://www.youtube.com/watch?v=EW521e8c8lk

### video starts 10:40

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:

        prefixsum = {}
        prefixsum[0] = True
        prev = 0
        res = 0
        for num in nums:
            curr = prev + num
            
            if curr - target in prefixsum:
                res += 1
                prefixsum = {}
                prefixsum[0] = True
                prev = 0
            
            else:
                prefixsum[curr] = True
                prev = curr
            
        print(res)
        return res
        
        
        
        



'''
It seems that I have exact the same idea as the following post
https://leetcode.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/discuss/780882/Java-14-lines-Greedy-PrefixSum-with-line-by-line-explanation-easy-to-understand

why does the following code now working???? 


### The following code does not pass submission ..... 
class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        prefixsum = {}
        prefixsum[0] = -1
        res = 0
        last = -1
        prev = 0
        for idx, num in enumerate(nums):
            curr = prev + num
            prefixsum[curr] = idx
            
            if curr - target in prefixsum:
                if prefixsum[curr - target] >= last:
                    res += 1
                    last = prefixsum[curr]
            prev = curr 
        print(prefixsum)
        print(res)
        return res


'''






class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        n = len(nums)
        dp = [0]*(n+1)
        dict = {}
        dict[0] = 0
        
        curr = 0
        
        for i in range(1,n+1):
            curr += nums[i-1]
            miss = curr - target
            if miss in dict:
                dp[i]= 1 + dp[dict[miss]]
                
            dp[i] = max(dp[i-1],dp[i])
            dict[curr]=i
            
        return dp[n]


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
      res = 0
      csum = [0]
      for n in nums:
        csum.append(csum[-1]+n)
      # print (csum[1:])
      # print ([c-target for c in csum[1:]])
      seen = set([])
      for c in csum[:]:
        # print (c, c-target, seen)
        if c-target in seen:
          res += 1
          seen.clear()
        seen.add(c)
        
      return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        csum = {}
        csum[0] = 0
        dp = [0 for i in range(len(nums)+1)]
        sum,best = (0,0)
        for i,v in enumerate(nums):
            sum += v
            x = sum - target
            dp[i+1] = dp[i]
            if x in csum:
                dp[i+1] = max(dp[i+1], dp[csum[x]] + 1)
            best = max(best, dp[i+1])
            csum[sum] = i + 1
        return best
            


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        count = 0
        sums = set()
        sums.add(0)
        tot = 0
        for num in nums:
            tot += num
            if (tot - target) in sums:
                count += 1
                sums=set()
            sums.add(tot)
        return count


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        lookup = {0 : -1}
        running_sum  = 0
        count = 0
        for i in range(len(nums)):
            running_sum += nums[i]
            if running_sum - target in lookup:
                count += 1
                lookup = {} #reset the map
            lookup[running_sum] = i
        return count

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        dp = [0] + [-1] * len(nums)
        s = 0
        dic = {}
        dic[0] = 0
        res = 0
        
        for i in range(len(nums)):
            s += nums[i]            
            if s - target in dic:
                dp[i+1] = max(dp[dic[s-target]] + 1, dp[i])
            else: 
                dp[i+1] = dp[i]
        
            dic[s] = i + 1
        print(dp)
        return dp[-1]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        for i in range(1, len(nums)):
            nums[i] += nums[i - 1]
        res = 0
        seen = {}
        used_i = 0
        nums = [0] + nums
        for i, num in enumerate(nums):
            if num - target in seen and seen[num - target] >= used_i:
                res += 1
                used_i = i
            seen[num] = i
        return res


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        prefix_sum = count = 0
        seen = {0}
        for num in nums:
            prefix_sum += num
            if prefix_sum - target in seen:
                prefix_sum = 0
                count += 1
                seen = set([0])
            seen.add(prefix_sum)
        return count

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        dic = {0:-1}
        acc = 0
        last = -1
        res = 0
        
        for i, n in enumerate(nums):
            acc += n
            
            if acc - target in dic and dic[acc-target] >= last:
                res += 1
                last = i
                
            dic[acc] = i
            
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        m = {0: 0}
        res = 0
        sum = 0
        for x in nums:
            sum += x
            if sum - target in m:
                res = max(res, m[sum - target] + 1)
            m[sum] = res
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        cache = set([0])
        cur, res = 0, 0
        for i in range(len(nums)):
            cur += nums[i]
            if cur - target in cache:
                res += 1
                cache.clear()
            cache.add(cur)
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        count = 0
        total = 0
        pastSums = set()
            
            
        for n in nums:
            total += n
            
            if total == target or total - target in pastSums:
                total = 0
                count += 1
                pastSums.clear()
            else:
                pastSums.add(total)
                
                
        return count

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        prefix_sum = count = 0
        prev_subarray_end = -1
        seen = {0 : -1}
        for i, num in enumerate(nums):
            prefix_sum += num
            if seen.get(prefix_sum - target, -2) >= prev_subarray_end:
                count += 1
                prev_subarray_end = i
            seen[prefix_sum] = i
        return count


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        dp = [0] + list(accumulate(nums))
        len_dp = len(dp)
        answer = 0
        lo = 0
        lo_sum = 0
        for hi in range(1, len_dp):
            if dp[hi] < lo_sum:
                lo_sum = dp[hi]
            if dp[hi] - lo_sum >= target:
                if dp[hi] - target in dp[lo:hi]:
                    answer += 1
                    lo = hi
                    lo_sum = dp[hi]
        return answer


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        curr = 0
        ans = 0
        seen = set()
        for num in nums:
            seen.add(curr)
            curr += num
            want = curr - target
            if want in seen:
                ans += 1
                seen = set()
                curr = 0
        return ans

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        psum = [0]
        for v in nums:
            psum.append(v+psum[-1])
        
        
        
        def helper(lo, target):
            d = {psum[lo-1]}
            ans = 0
            for i in range(lo, len(psum)):
                if psum[i] - target in d:
                    ans = 1 + helper(i+1, target)
                    break
                d.add(psum[i])
            return ans
        
        return helper(1, target)


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        cum_map = {
            0: -1,
        }
        intervals = [-1] * len(nums)
        cur = 0
        for i, x in enumerate(nums):
            cur += x
            rest = cur - target
            boundary = cum_map.get(rest)
            if boundary is not None:
                intervals[i] = boundary + 1
            cum_map[cur] = i
        
        
        res = 0
        s = [0] * len(nums)
        for i in range(len(nums)):
            if intervals[i] == i:
                s[i] = s[i-1] + 1
                continue
            
            s[i] = s[i-1]
            if intervals[i] == 0:
                s[i] = max(s[i-1], 1)
            elif intervals[i] > 0:
                s[i] = max(s[i-1], s[intervals[i] - 1] + 1)
                
        return s[-1]                
                


from collections import defaultdict
from bisect import *

class Solution:
    def maxNonOverlapping(self, lst: List[int], k: int) -> int:

        n     = len(lst)
        first = 0 
        last  = 0
        total = lst[0]
        
        dct   = defaultdict(list)
        
        dp = [0 for i in range(n+1)]
        
        for i in range(1,n+1):
            dp[i] = dp[i-1]+lst[i-1]
            dct[dp[i]].append(i)
        
    
        intervals = [ ]
        for i in range(n+1):
            # for temp in dct[k+dp[i]]:
            #     if(temp>i):
            #         intervals.append((i,temp))
            
            left = bisect_right(dct[k+dp[i]],i)
            if(left!=len(dct[k+dp[i]])):
                intervals.append((i,dct[k+dp[i]][left]))

        
        intervals.sort(key = lambda x:x[1])
        
        pre = -float('inf')
        ans = 0 
        index = 0
        
        print(intervals)
        
        while(index<len(intervals)):
            if(intervals[index][0]>=pre):
                ans+=1
                pre = intervals[index][1]
            index+=1
        return ans
        
                
                
            
            
                


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        pref = {}
        pref[0] = -1
        ans = 0
        presum = 0
        j = -1
        for i in range(len(nums)):
            presum += nums[i]
            c = presum - target
            if c in pref and pref[c] >= j:
                ans += 1
                j = i
            pref[presum] = j
        return ans


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        N = len(nums)
        
        prefix_sum = [0 for _ in range(N)]
        prefix_sum[0] = nums[0]
        for i in range(1, N):
            prefix_sum[i] = nums[i] + prefix_sum[i-1]
        
        prev_prefix = {}
        last_index = -1
        subarrays = 0
        for i in range(N):
            prefix = prefix_sum[i]
            
            to_look = prefix - target
            if to_look in prev_prefix and prev_prefix[to_look] >= last_index:
                last_index = i
                subarrays += 1
            elif nums[i] == target:
                subarrays += 1
                last_index = i
            elif prefix == target and last_index == -1:
                subarrays += 1
                last_index = i
                
            prev_prefix[prefix] = i
            
        return subarrays

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = [0] * (n+1)
        dic = {}
        dic[0] = 0
        curr = 0
        
        for i in range(1, n+1):
            curr += nums[i-1]
            if curr - target in dic:
                dp[i] = dp[dic[curr-target]] + 1
            dp[i] = max(dp[i-1], dp[i])
            dic[curr] = i
            
        return dp[-1]

class Solution:
    
    def maxNonOverlapping(self, nums, target) -> int:
        hashMap = {0: -1} #totalSum -> inclusive ending index
        totalSum = 0
        answer = []
        count = 0
        for i in range(len(nums)):
            totalSum += nums[i]
            if totalSum - target in hashMap:
                answer.append([hashMap[totalSum-target] + 1, i])
            
            hashMap[totalSum] = i

        ending = None
        for i in answer:
            if ending is None or i[0] > ending:
                count += 1
                ending = i[1]
        return count 


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        D = {0:-1}
        cumsum = 0
        idx = -1
        res = 0
        for i, x in enumerate(nums):
            cumsum += x
            if cumsum - target in D and D[cumsum-target] >= idx:
                res += 1
                idx = i
            D[cumsum] = i
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        s = set()
        s.add(0)
        ans = 0
        prefsum = 0
        for num in nums:
            prefsum += num
            if prefsum - target in s:
                ans += 1
                s = set()
            s.add(prefsum)
        return ans

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        dp = [0] * (len(nums)+1)
        acc = [0] * (len(nums)+1)
        sumDict = {0:0}
        for k, ele in enumerate(nums):
            dk = k+1
            acc[dk] = acc[k] + ele
            if acc[dk]-target in sumDict:
                dp[dk] = max(dp[k], dp[sumDict[acc[dk]-target]]+1)
            else:
                dp[dk] = dp[k]
                
            sumDict[acc[dk]] = dk
        
        return dp[len(nums)]


from collections import defaultdict
class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        cum_sum=[0]
        for i in range(len(nums)): cum_sum.append(cum_sum[-1]+nums[i])

        mem=defaultdict(list)

        for i in range(len(nums)+1):
            mem[cum_sum[i]].append(i)

        def binSearch(index):
            arr=mem[cum_sum[index]-target]
            right=len(arr)-1
            left=0
            best=None
            while left<=right:
                mid=(left+right)//2
                if arr[mid]<index:
                    best=arr[mid]
                    left=mid+1
                else:
                    right=mid-1
            return best

        dp=[0 for i in range(len(nums)+1)]
        for i in range(1,len(nums)+1):
            ind=binSearch(i)
            s=0
            if ind!=None:
                s=1+dp[ind]
            dp[i]=max(dp[i-1],s)

        return dp[-1]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        N = len(nums)
        
        prefix_sum = [0 for _ in range(N)]
        prefix_sum[0] = nums[0]
        for i in range(1, N):
            prefix_sum[i] = nums[i] + prefix_sum[i-1]
        
        # TODO: there is a bug here..not sure what the hell it is though!!!!
        prev_prefix = {}
        last_index = -1
        subarrays = 0
        for i in range(N):
            prefix = prefix_sum[i]
            
            to_look = prefix - target
            if to_look in prev_prefix and prev_prefix[to_look] >= last_index:
                last_index = i
                subarrays += 1
            elif nums[i] == target:
                subarrays += 1
                last_index = i
            elif prefix == target and last_index == -1:
                subarrays += 1
                last_index = i
                
            prev_prefix[prefix] = i
                
            
        return subarrays


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        prefix_sum = 0
        seen = {0}
        res = 0
        for n in nums:
            prefix_sum += n
            if prefix_sum - target in seen:
                seen = {prefix_sum}
                res += 1
            seen.add(prefix_sum)
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        # Taking a walk through the array, if we can ever make the target, we might as well because we'd like the border for the last subarray to be as far left as possible for the next. To see if we can make the target, we just take the total sum so far and see if we ever had the right previous total sum to chop off. We also check that the chop point does not overlap another subarray end point we used.
        #maintain a list of end indices
        hmap = collections.defaultdict(int)
        rsum = 0
        res = 0
        last = -1
        hmap[0] = -1
        
        for index,num in enumerate(nums):
            
            rsum += num
            
            csum = rsum - target
            
            # if rsum == target:
            #     res += 1
            
            if csum in hmap and hmap[csum] >= last:
                res += 1
                last = index
                
            hmap[rsum] = index
            
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        run_sum = 0
        count = 0
        book_keep = {0:1}
        for num in nums:
            run_sum += num
            prev_sum = run_sum - target
            if prev_sum in book_keep:
                count += 1
                run_sum = 0
                book_keep.clear()
                book_keep = {0:1}
            else:
                book_keep[run_sum] = 1
        
        return count  
                
                
            
            
            
                    
        
            
            
        


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        for i in range(1, n):
            nums[i] += nums[i-1]
        seen = {0: 0}
        res = 0
        for i, n in enumerate(nums):
            if n-target in seen:
                res += 1
                seen = {n:0}
            else:
                seen[n] = i
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        pre = 0
        sums = [0]
        for el in nums:
            pre += el
            sums.append(pre)
            
        #print(\"---\")
       # print(sums)
        ans = 0
        seen = {} # seen[v] = i iff sums[i] == v
        for i, v in enumerate(sums):
            #print(f\"seen: {seen}\")
            if v-target in seen:
                ans += 1
                seen = {} # satisfies non-overlapping
            seen[v] = i
        #print(f\"seen: {seen}\")
        return ans
            


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        hashmap = {0:0}
        ans = 0
        sums = 0
        for i in range(n):
            sums += nums[i]
            if sums-target in hashmap:
                ans = max(ans, hashmap[sums-target] + 1)
            hashmap[sums] = ans
        return ans
        
        
        # n = len(nums)
        # preSum = [0 for i in range(n+1)]
        # hashmap = {0:0}
        # lastend = 0
        # ans = 0
        # for i in range(1, n+1):
        #     preSum[i] = preSum[i-1] + nums[i-1]
        #     begin = hashmap.get(preSum[i]-target, -1)
        #     if begin >= 0 and begin >= lastend:
        #         lastend = i
        #         ans += 1
        #     pos = hashmap.get(preSum[i], 0)
        #     hashmap[preSum[i]] = max(pos, i)
        # return ans
        
        # n = len(nums)
        # dp = [0 for i in range(n+1)]
        # for i in range(n):
        #     tmpsum = 0
        #     for j in range(i, -1, -1):
        #         tmpsum += nums[j]
        #         if tmpsum == target:
        #             dp[i+1] = max(dp[i+1], dp[j] + 1)
        #         else:
        #             dp[i+1] = max(dp[i+1], dp[j])
        # print(dp)
        # return dp[n]
        
        
        # n = len(nums)
        # dp = [0 for i in range(n)]
        # if target == nums[0]:
        #     dp[0] = 1
        # for i in range(1, n):
        #     tmpsum = 0
        #     for j in range(i, -1, -1):
        #         tmpsum += nums[j]
        #         if tmpsum == target:
        #             if j > 0:
        #                 dp[i] = max(dp[i], dp[j-1] + 1)
        #             else:
        #                 dp[i] = max(dp[i], 1)
        #             break
        # print(dp)
        # return dp[n-1]


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        prefix =[0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        seen = {0:0}
        ans = 0
        for i in range(1,n + 1):
            current = prefix[i]
            a = current - target
            if a in seen:
                ans += 1
                seen = {}
            seen[current] = 1
        return ans

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        sums=set()
        s=0
        cnt=0
        sums.add(0)
        
        for n in nums:
            s+=n
            if s-target in sums:
                cnt+=1
                sums=set()
            
            sums.add(s)
                
        return cnt
            

                    
                    
                


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        h = {0: 1}
        summ = count = 0
        for i in range(0, len(nums)):
            summ += nums[i]
            if summ - target in h:
                count += 1
                h = {}
            h[summ] = i
            
        return count


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        if not nums: return 0
        
        seen = set([0])
        
        out = 0
        
        curr = 0
        
        for i in nums:
            curr += i
            if curr - target in seen:
                out += 1
                seen = set([0])
                curr = 0
            else:
                seen.add(curr)
        
        return out

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        res = 0
        cumsum = 0
        cache = set([0])
        for num in nums:
            cumsum += num
            if cumsum - target in cache:
                res += 1
                cache = set()
            cache.add(cumsum)
                
        return res


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        count = 0
        curr_cnt = 0
        dic = {0:-1}
        for i in range(len(nums)):
            curr_cnt += nums[i]
            if curr_cnt - target in dic:
                count += 1
                dic = {}
            dic[curr_cnt] = i
        return count
        


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        tot = 0
        seen = set([0])
        cur = 0
        for n in nums:
            cur += n
            if cur - target in seen:
                tot += 1
                cur = 0
                seen = set([0])
            else:
                seen.add(cur)
        return tot


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        # n = len(nums)
        # hashmap = {0:0}
        # ans = 0
        # sums = 0
        # for i in range(n):
        #     sums += nums[i]
        #     if sums-target in hashmap:
        #         ans = max(ans, hashmap[sums-target] + 1)
        #     hashmap[sums] = ans
        # return ans
        
        
        n = len(nums)
        preSum = [0 for i in range(n+1)]
        hashmap = {0:0}
        lastend = 0
        ans = 0
        for i in range(1, n+1):
            preSum[i] = preSum[i-1] + nums[i-1]
            begin = hashmap.get(preSum[i]-target, -1)
            if begin >= 0 and begin >= lastend:
                lastend = i
                ans += 1
            hashmap[preSum[i]] = i
        return ans
        
        # n = len(nums)
        # dp = [0 for i in range(n+1)]
        # for i in range(n):
        #     tmpsum = 0
        #     for j in range(i, -1, -1):
        #         tmpsum += nums[j]
        #         if tmpsum == target:
        #             dp[i+1] = max(dp[i+1], dp[j] + 1)
        #         else:
        #             dp[i+1] = max(dp[i+1], dp[j])
        # print(dp)
        # return dp[n]
        
        
        # n = len(nums)
        # dp = [0 for i in range(n)]
        # if target == nums[0]:
        #     dp[0] = 1
        # for i in range(1, n):
        #     tmpsum = 0
        #     for j in range(i, -1, -1):
        #         tmpsum += nums[j]
        #         if tmpsum == target:
        #             if j > 0:
        #                 dp[i] = max(dp[i], dp[j-1] + 1)
        #             else:
        #                 dp[i] = max(dp[i], 1)
        #             break
        # print(dp)
        # return dp[n-1]


class Solution:
  def maxNonOverlapping(self, nums: List[int], target: int) -> int:
    # TC: O(N), SC:O(N)
    n = len(nums)
    # prefix sum
    for i in range(1, n):
      nums[i] += nums[i - 1]
    seen, dp = {0: -1}, [0] * n
    for i in range(n):
      x = nums[i] - target
      if x in seen:
        dp[i] = max(dp[i - 1], dp[seen[x]] + 1)
      else:
        dp[i] = dp[i - 1]
      seen[nums[i]] = i
    return dp[-1]

from typing import List, Tuple
class Solution:
    def maxNonOverlappingIntervals(self, intervals: List[Tuple[int, int]], sort=True) -> int:
        if not intervals:
            return 0
        # Sort intervals by ending time
        if sort:
            intervals = sorted(intervals, key=lambda x: x[1])
        ans = 1
        cur_end = intervals[0][1]
        for start, end in intervals[1:]:
            if start <= cur_end:
                continue
            ans += 1
            cur_end = end
        return ans
        
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        # If we can get all subarrays that sum to target in order sorted by ending index,
        # then we can simply apply activity selection to it.
        # We can use prefix sums to get this^^. Note that because negative numbers are allowed,
        # we might get multiple subarrays ending at i that sum to target. However, we can ignore
        # all except the smallest one, as we want non-overlapping.
        prefix_sum = {0: -1}
        cumsum = 0
        intervals = []
        for i, x in enumerate(nums):
            cumsum += x
            if cumsum - target in prefix_sum:
                intervals.append((prefix_sum[cumsum-target]+1, i))
            prefix_sum[cumsum] = i  # Don't bother with multiple indices, just use the the latest one
        return self.maxNonOverlappingIntervals(intervals, False)

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        presum = 0
            
        last_pos = {0: 0}
        dp = [0] * (1 + n)
        for i in range(1, 1 + n):
            presum += nums[i - 1]
            dp[i] = dp[i - 1]
            if presum - target in last_pos:
                pos = last_pos[presum - target]
                dp[i] = max(dp[i], dp[pos] + 1)
            last_pos[presum] = i
        # print(dp)
        return dp[n]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        dp=[0]*(1+len(nums))
        mem={0:0}
        cur=0
        for i,v in enumerate(nums):
            cur+=v
            dp[i+1]=dp[i]
            if cur-target in mem:
                dp[i+1]=max(dp[i+1],dp[mem[cur-target]]+1)
            mem[cur]=i+1
        # print(dp)
        return dp[-1]


# idea: greedy. keep a check of cumulated sum, and as soon as we find a subarray whose sum equals target, we reset cumulated sum

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        cum_sum = 0
        seen_cum_sum = set([0])
        count = 0
        
        for num in nums:
            cum_sum += num
            complement = cum_sum-target
            
            if complement in seen_cum_sum:
                count += 1
                cum_sum = 0
                seen_cum_sum = set([0])
                
            seen_cum_sum.add(cum_sum)
                
        return count

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        prefixSum = {0:-1}
        dp = [0] * len(nums)
        
        currSum = 0
        for i in range (len(nums)):
            currSum = currSum + nums[i]
            if currSum - target in prefixSum:
                end = prefixSum[currSum - target]
                dp[i] = max(1 + dp[end], dp[i-1])
            elif i == 0:
                dp[i] = 0
            else:
                dp[i] = dp[i-1]
            prefixSum[currSum] = i
        return dp[len(nums)-1]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
      
        prefix = {0:-1}
        cur = 0
        res = 0
        for i,v in enumerate(nums):  
          cur += v
          if (cur - target) in prefix:
            res += 1
            prefix = {}
            
          prefix[cur] = i

        return res
            
          


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        '''
        Get prefix sum: pref[]
        Find the largest sorted list of indices index[] where
        pref[index[1]] - pref[index[0]] = pref[index[3]] - pref[index[2]] = ... = target
        '''
        pref = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            pref[i+1] = pref[i] + nums[i]
        
        d = {}
        ans = 0
        #print(pref)
        for i in range(len(pref)):
            #print(pref[i], d)
            if pref[i] - target in d:
                ans += 1
                #print(ans)
                d.clear()
            d[pref[i]] = i
        return ans


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        d={0:-1}
        add=0
        count=0
        i=0
        while(i<=len(nums)-1):
            add+=nums[i]
            if (add-target) in d :
                count+=1
                d= {}
            d[add]=i
            i+=1
        return count    
                    


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        prefix = list(itertools.accumulate(nums))
        
        def dfs(i):
            s = {prefix[i - 1] if i > 0 else 0}
            for j in range(i, len(prefix)):
                if prefix[j] - target in s:
                    return 1 + dfs(j + 1)
                s.add(prefix[j])
            return 0
        
        return dfs(0)

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        count, sums, curr = 0, {0}, 0
        for num in nums:
            curr += num
            if curr - target in sums:
                count += 1
                sums.clear()
            sums.add(curr)
        return count


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
            
        ans = 0
        seen = {0:0}
        for i in range(1,n + 1):
            curr = prefix[i]
            a = curr - target
            if a in seen:
                ans += 1
                seen = {}
                
            seen[curr] = i
        return ans

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        presum = [0]
        for num in nums:
            presum.append(presum[-1] + num)
            
        last_pos = {0: 0}
        dp = [0] * (1 + n)
        for i in range(1, 1 + n):
            dp[i] = dp[i - 1]
            if presum[i] - target in last_pos:
                pos = last_pos[presum[i] - target]
                
                dp[i] = max(dp[i], dp[pos] + 1)
            last_pos[presum[i]] = i
        # print(dp)
        return dp[n]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        preSum = [0]
        for num in nums:
            preSum.append(preSum[-1] + num)
            
        n = len(nums)
        dp = [0 for i in range(n + 1)]
        
        temp = {0:0}
        for i in range(1, n + 1):
            dp[i] = dp[i - 1]
            if preSum[i] - target in temp:
                dp[i] = max(dp[i], dp[temp[preSum[i] - target]] + 1)
            temp[preSum[i]] = i
        
        return dp[n]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        N = len(nums)
        
        rtv = 0

        presum = dict()
        presum[0] = -1
        total = 0
        for i,v in enumerate(nums):
            total += v
            
            ne = total - target
            if ne in presum and presum[ne] < i:
                rtv += 1
                # print(\"{} {}\".format(presum[ne]+1, i))

                presum = dict()
                presum[0] = i
                total = 0
            else:
                presum[total] = i

        return rtv

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        ln = len(nums)
        ret = 0
        
        sums = {0 : 0}
        dp = [0] * (ln+1)

        s = 0
        for i in range(ln):
            s += nums[i]
            
            if s - target in sums:
                idx = sums[s-target]
                dp[i+1] = 1 + dp[idx]
                
            dp[i+1] = max(dp[i], dp[i+1])
            
            sums[s] = i+1
                
        
        
        return dp[ln]
        pass


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        subarrays = []
        summ = 0
        lookup = set([0])
        count = 0
        for num in nums:
            summ += num
            if summ - target in lookup:
                count += 1
                summ = 0
                lookup = set([0])
            else:
                lookup.add(summ)
        return count 


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        if len(nums) == 0:
            return 0
        
        h = {}
        dp = []
        s = nums[0]
        if s == target:
            dp.append(1)
        else:
            dp.append(0)
        h[s] = 0
        for i in range(1, len(nums)):
            s = s + nums[i]
            if s == target:
                if 0 in h:
                    dp.append(max(dp[h[0]]+1, dp[-1]))
                else:
                    dp.append(max(1, dp[-1]))
            elif s-target in h:
                dp.append(max(dp[h[s-target]]+1, dp[-1]))
            else:
                dp.append(dp[-1])
            h[s] = i
        return dp[-1]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        d = {0: -1}
        cursum = 0
        ans = 0
        for i,n in enumerate(nums):
            cursum += n
            prev = cursum - target
            if prev in d:
                ans += 1
                d = {}
            
            d[cursum] = i
        
        return ans

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        cur = 0
        n = len(nums)
        dp = [0]*(n+1)
        dic = {}
        dic[0]=0
        
        for i in range(1,n+1):
            cur+=nums[i-1]
            if cur-target in dic:
                dp[i] = 1+dp[dic[cur-target]]
            dp[i] = max(dp[i],dp[i-1])
            
            dic[cur]=i
        
        return dp[n]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        seen = {0:0}
        ans = 0
        for i in range(1,n + 1):
            cur = prefix[i]
            a = cur - target
            if a in seen:
                ans += 1
                seen = {}
            seen[cur] = 1
        return ans

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        dp = [0] * (len(nums) + 1)
        mem = dict()
        mem[0] = -1
        cur = 0
        for i in range(1, len(nums) + 1):
            dp[i] = dp[i - 1]
            cur += nums[i - 1]
            t = cur - target
            #print(i-1, cur, t, mem)
            if t in mem:
                dp[i] = max(dp[i], dp[mem[t]] + 1)
                #print('!!', i, dp)
            mem[cur] = i
        return dp[-1]
        


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        sm = 0
        hsh = {}
        dp = {}
        dp[-1] = 0
        ans = 0
        for i in range(len(nums)):
            dp[i] = dp[i-1]
            sm += nums[i]

            if sm - target in hsh:
                dp[i] = max(dp[i], dp[hsh[sm-target]] + 1)
                
            hsh[sm] = i
            if sm == target:
                dp[i] = max(dp[i], 1)
            ans = max(ans, dp[i])
        return ans


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        cnt = collections.Counter()
        cnt[0] = 0
        ans = 0
        prefix = 0
        for n in nums:
            prefix += n
            # if p
            if prefix-target in cnt:
                ans += 1
                cnt = collections.Counter()
            cnt[prefix] += 1
            # print(cnt, ans)
        # print('--')
        return ans
    
    
#         dic = {0:0}
#         ans = 0
#         sum = 0
#         for i in range(len(nums)):
#             sum+=nums[i]
#             if sum-target in dic:
#                 ans+=1
#                 dic = {}
#             dic[sum] = i
#         return ans


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
            
        seen = {0:0}
        ans = 0
        for i in range(1,n + 1):
            curr = prefix[i]
            a = curr - target
            if a in seen:
                ans += 1
                seen = {}
                
            seen[curr] = i
        return ans

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        
        d = {0:1}
        
        total = 0
        count = 0
        
        for i in nums:
            total += i
            
            
            if total - target in d:
                print(total)
                count += 1
                d = {0:1}
                total = 0
            
            else :
                d[total] = 1
                
        return count
        
        
            
        
        
        
        
        


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        pos={0:-1}
        n=len(nums)
        dp=[0]*(n+1)
        s=0
        for i in range(n):
            s+=nums[i]
            dp[i+1]=dp[i]
            t=s-target
            if t in pos:
                dp[i+1]=max(dp[i+1],dp[pos[t]+1]+1)
            pos[s]=i
        return dp[-1]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        pref_sum = [0 for _ in range(n + 1)]
        
        for i in range(n):
            pref_sum[i + 1] = pref_sum[i] + nums[i]
        
        dp = collections.defaultdict(lambda: -1)
        cur_max = 0
        dp[0] = 0
        for pref in range(1, n + 1):
            cur_max = max(cur_max, dp[pref_sum[pref] - target] + 1)
            dp[pref_sum[pref]] = cur_max
        return cur_max

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = [0 for i in range(n+1)]
        d = {}
        d[0] = -1
        s = 0
        for i in range(n):
            s+=nums[i]
            t = s-target
            dp[i+1] = dp[i]
            if t in d:
                dp[i+1] = max(dp[i+1],dp[d[t]+1]+1)
            d[s] = i
        # print(d)
        return dp[n]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        
        dp = [0] * (n+1)
        
        dic = {}
        dic[0] = 0
        
        cur = 0 
        
        for i in range(1, n+1):
            cur += nums[i - 1]
            
            if cur - target in dic:
                dp[i] = 1 + dp[dic[cur - target]]
            dp[i] = max(dp[i-1], dp[i])
            
            dic[cur] = i 
        return dp[n]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        preSum = [0 for i in range(n+1)]
        hashmap = {0:0}
        lastend = 0
        ans = 0
        for i in range(1, n+1):
            preSum[i] = preSum[i-1] + nums[i-1]
            begin = hashmap.get(preSum[i]-target, -1)
            if begin >= 0 and begin >= lastend:
                lastend = i
                ans += 1
            pos = hashmap.get(preSum[i], 0)
            hashmap[preSum[i]] = max(pos, i)
        return ans
        
        
        
        
        # n = len(nums)
        # dp = [0 for i in range(n)]
        # ans = 0
        # if target == nums[0]:
        #     dp[0] = 1
        # for i in range(1, n):
        #     dp[i] = dp[i-1]
        #     tmpsum = 0
        #     for j in range(i, -1, -1):
        #         tmpsum += nums[j]
        #         if tmpsum == target:
        #             if j > 0:
        #                 dp[i] = max(dp[i], dp[j-1] + 1)
        #             else:
        #                 dp[i] = max(dp[i], 1)
        #             break
        # # print(dp)
        # return dp[n-1]


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        seen = set()
        seen.add(0)
        curr = 0
        res = 0
        for n in nums:
            curr += n
            if curr-target in seen:
                res += 1
                curr = 0
                seen = set([0])
            else:
                seen.add(curr)
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        d = {0:True}
        sm = 0
        count = 0
        for i in nums:
            sm += i
            if sm-target in d:
                count += 1
                sm = 0
                d = {0:True}
            else:
                d[sm] = True
            # print(sm,count)
        return count

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        subarrays = []
        summ = 0
        lookup = set()
        count = 0
        lookup.add(0)
        for num in nums:
            summ += num
            if summ - target in lookup:
                count += 1
                summ = 0
                lookup = set([0])
            else:
                lookup.add(summ)
        return count 


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        prefix_sum = [0] * n    # prefix_sum[i] = sum of nums[0...i] inclusive
        lookup = {}             # lookup[sum] = rightmost index st prefix_sum[idx] == sum
        dp = [0] * n            # dp[i] = most non overlapping subarrays = target in nums[0...i]
                                # dp[i] = max(dp[i - 1], dp[j] + 1 (if j+1...i == target)) if i > 0
                                # dp[0] = 1 if nums[0] == target else 0
        dp[0] = 1 if nums[0] == target else 0
        prefix_sum[0] = nums[0]
        lookup[nums[0]] = 0
        for i in range(1, len(nums)):
            prefix_sum[i] = prefix_sum[i - 1] + nums[i]
            check_for = prefix_sum[i] - target
            cmp_val = 0
            if check_for in lookup:
                cmp_val = dp[lookup[check_for]] + 1                
            elif check_for == 0:
                cmp_val = 1
            dp[i] = max(dp[i - 1], cmp_val)
            lookup[prefix_sum[i]] = i
            
        return dp[-1]
    
        # 0 0 0
        # prefix_sum    [0, 0]
        # lookup        {0:1}
        # dp            [1, ]


class Solution:
    def maxNonOverlapping(self, nums, target):
        d = {0: -1}
        prefix = 0
        count = 0
        for i in range(len(nums)):
            prefix += nums[i]
            found = prefix - target
            if found in d:
                count += 1
                d = {}
            d[prefix] = i
        return count

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        pos = {0: 0}
        cumsum = 0
        ans = 0
        
        for num in nums:
            cumsum += num
            pos[cumsum] = max(ans, pos.get(cumsum-target, -1)+1)
            ans = max(ans, pos[cumsum])
            #print(pos, cumsum)
        return ans


class Solution:
    def maxNonOverlapping(self, A: List[int], T: int) -> int:
        N = len(A)
        prefix_sum = [0 for _ in range(N + 1)]
        for i in range(1, N + 1):
            prefix_sum[i] = prefix_sum[i - 1] + A[i - 1]
        seen = set([0])
        res = 0
        for i in range(N):
            curr = prefix_sum[i + 1]
            want = curr - T
            if want in seen:
                res += 1
                seen = set()
            seen.add(curr)
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        cnt = collections.Counter()
        cnt[0] = 1
        ans = 0
        prefix = 0
        for n in nums:
            prefix += n
            if cnt[prefix-target]!=0:
                ans += 1
                cnt = collections.Counter()
                cnt[0] = 0
            cnt[prefix] += 1
            # print(cnt, ans)
        print('--')
        return ans

from collections import defaultdict
class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
#         cum_sum=[0]
#         for i in range(len(nums)): cum_sum.append(cum_sum[-1]+nums[i])

#         mem=defaultdict(list)

#         for i in range(len(nums)+1):
#             mem[cum_sum[i]].append(i)

#         def binSearch(index):
#             arr=mem[cum_sum[index]-target]
#             right=len(arr)-1
#             left=0
#             best=None
#             while left<=right:
#                 mid=(left+right)//2
#                 if arr[mid]<index:
#                     best=arr[mid]
#                     left=mid+1
#                 else:
#                     right=mid-1
#             return best

#         dp=[0 for i in range(len(nums)+1)]
#         for i in range(1,len(nums)+1):
#             ind=binSearch(i)
#             s=0
#             if ind!=None:
#                 s=1+dp[ind]
#             dp[i]=max(dp[i-1],s)

#         return dp[-1]
        dp=[0 for i in range(len(nums)+1)]
        mp={}
        s=0
        mp[0]=0
        for i in range(1,len(nums)+1):
            s+=nums[i-1]
            dp[i]=dp[i-1]
            if s-target in mp:
                dp[i]=max(dp[i],1+dp[mp[s-target]])
            if nums[i-1]==target:
                dp[i]=max(dp[i],1+dp[i-1])
            mp[s]=i
        return dp[-1]




class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        sett = set([0])
        ans = 0
        cur = 0
        for val in nums:
            cur += val
            if cur - target in sett:
                ans += 1
                sett = set()
            sett.add(cur)
        return ans

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        prefix = [0]*(len(nums)+1)
        counts = defaultdict(int)
        counts[0] = 1
        tot = 0
        for i in range(1,len(nums)+1):
            prefix[i] = nums[i-1] + prefix[i-1]
            if counts[prefix[i]-target] != 0:
                tot += 1
                counts = defaultdict(int)
                prefix[i] = 0
            counts[prefix[i]] += 1
        return tot


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        walk = {0:-1}
        prefixSum = 0
        delimiter = -1
        res = 0
        for i in range(len(nums)):
            prefixSum += nums[i]
            remain = prefixSum - target
            if (remain in walk.keys() and walk[remain] >= delimiter):
                res += 1
                delimiter = i
            walk[prefixSum] = i
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        d = {0: -1}
        cursum = 0
        ans = 0
        for i,n in enumerate(nums):
            cursum += n
            prev = cursum - target
            if prev in d:
                ans += 1
                d = {}
                d[cursum] = i
                continue
            
            d[cursum] = i
        
        return ans


class Solution:
    def maxNonOverlapping(self, arr: List[int], target: int) -> int:
        prevSums, n = {0: -1}, len(arr)
        prefixSum, count, lastIndex = 0, 0, -1
        
        for i in range(n):
            prefixSum += arr[i] 
            rem = prefixSum - target
            if rem in prevSums and prevSums[rem] >= lastIndex:
                count += 1 
                lastIndex = i
            prevSums[prefixSum] = i
        return count

# idea: greedy. keep a check of cumulated sum, and as soon as we find a subarray whose sum equals target, we reset cumulated sum

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        cum_sum = 0
        seen_cum_sum = set([0])
        count = 0
        
        for num in nums:
            cum_sum += num
            complement = cum_sum-target
            
            # if we found a subarray whose sum equals target, we reset cumulated sum
            if complement in seen_cum_sum:
                count += 1
                cum_sum = 0
                seen_cum_sum = set([0])
                
            seen_cum_sum.add(cum_sum)
                
        return count

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        # if nums[0:j] sum larger than target and there is a subarry nums[i:j] sum equal to target
        # then sum(0:j)-sum(0:i) == target
        # base on this idea, we could store each prefix_sum in to a map, 
        # check whether sum(0:j)-target is in the prefix_sum map. 
        # since we need overlapping, so store the right_most index for each prefix sum
        # update the just found subarry's rightmose index, check current end index
        
        map = {0:-1}
        prefix, rightmost, count = 0, -1, 0
        
        for i,val in enumerate(nums):
            prefix += val
            if prefix-target in map and map[prefix-target]>=rightmost: # for overlapping
                count += 1
                rightmost = i
                
            map[prefix] = i
            
        return count


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        s = {0}
        res = 0
        cur = 0
        for x in nums:
            cur += x
            if cur - target in s:
                #print(x)
                res += 1
                cur = 0
                s = {0}
                continue
            s.add(cur)
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        sums = [0 for num in nums]
        sum2index = {0:-1}
        nums_subarrays = [0 for num in nums]
        for i, num in enumerate(nums):
            if i == 0:
                sums[i] = nums[i]
            else:
                sums[i] = sums[i-1] + nums[i]
            if sums[i]-target in sum2index:
                if i == 0:
                    nums_subarrays[i] = 1
                else:
                    nums_subarrays[i] = max(nums_subarrays[i-1], nums_subarrays[sum2index[sums[i]-target]]+1)
            else:
                if i == 0:
                    nums_subarrays[i] = 0
                else:
                    nums_subarrays[i] = nums_subarrays[i-1]
            sum2index[sums[i]] = i
        return nums_subarrays[-1]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        result = 0
        pre_sum = [0] * (n+1)
        for i,num in enumerate(nums):
            pre_sum [i+1] = pre_sum[i] + num

        seen = {0:0}
        for i in range(1,n+1):
            cur = pre_sum[i]
            if cur-target in seen:
                result += 1
                seen = {}
            seen[cur] = i
        return result

class Solution:
    
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        if len(nums) == 0:
            return 0
        result = 0
        
        # target = 10
        # [-2,6, 6, 3, 5, 4, 1, 2, 8]
        # [-2,4,10,13,18,22,23,25,33]
        #                         ^
        # seen: [0]
        # result = 2
        
        prefixSums = []
        partial = 0
        
        seen = set([0])
        
        for i in range(len(nums)):
            partial += nums[i]
            prefixSums.append(partial)
            required = prefixSums[i] - target
            if required in seen:
                result += 1
                seen = set()
            seen.add(prefixSums[i])
            
        return result
        
        


class Solution:
    def maxNonOverlapping(self, nums: list, target: int) -> int:
        sumDict=collections.defaultdict(collections.deque)
        preSum=0;sumDict[0].append(-1);right=-1;ans=0
        for i in range(len(nums)):
            preSum+=nums[i]
            if preSum-target in sumDict:
                while sumDict[preSum-target] and sumDict[preSum-target][0]<right:
                    sumDict[preSum-target].popleft()
                if sumDict[preSum-target]:
                    ans+=1
                    right=i
            sumDict[preSum].append(i)
        return ans

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        presum = [0] * (n + 1)
        for i in range(n):
            presum[i+1] = presum[i] + nums[i]
            
        seen = {0: 0}
        ans = 0
        for i in range(1, n + 1):
            curr = presum[i]
            prev = curr - target
            if prev in seen:
                ans += 1
                seen = {}
            seen[curr] = i
        
        return ans

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = [0] * (n+1)
        m = {0: 0}
        for i, pre in enumerate(itertools.accumulate(nums)):
            if pre-target in m:
                dp[i+1] = max(dp[i], dp[m[pre-target]]+1)
            else:
                dp[i+1] = dp[i]
            m[pre] = i+1
        return dp[-1]


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
#         n = len(nums)
#         prefix = [0] * (n + 1)
#         idx = []
#         for i in range(1, n + 1):
#             prefix[i] = prefix[i - 1] + nums[i - 1]
#         for i in range(n + 1):
#             for j in range(i + 1, n + 1):
#                 if prefix[j] - prefix[i] == target:
#                     idx.append([i, j])
#                     break

#         self.ans = 0        
#         def backtrk(cur, start):
#             if start == len(idx):
#                 self.ans = max(self.ans, len(cur))
#                 return
#             visited = set()
#             for i in range(start, len(idx)):
#                 if len(cur) >= 1 and idx[i][0] < cur[-1][1]:
#                     continue
#                 x, y = idx[i][0], idx[i][1]   
#                 backtrk(cur + [(x, y)], i + 1)
#         backtrk([], 0)
#         return self.ans
               
        prefix = [0]
        for x in nums:
            prefix.append(prefix[-1]+x)
        res = 0 
        seen = set()
        for x in prefix:
            if x-target in seen:
                res += 1
                seen = {x}
            else:
                seen.add(x)
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        #maintain a list of end indices
        hmap = collections.defaultdict(int)
        rsum = 0
        res = 0
        last = -1
        hmap[0] = -1
        
        for index,num in enumerate(nums):
            
            rsum += num
            
            csum = rsum - target
            
            # if rsum == target:
            #     res += 1
            
            if csum in hmap and hmap[csum] >= last:
                res += 1
                last = index
                
            hmap[rsum] = index
            
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        seen = {0: -1}
        prev = -1
        count = 0
        curr = 0
        for i in range(len(nums)):
            curr += nums[i]
            if nums[i] == target or (curr - target in seen and prev < seen[curr - target] + 1):
                prev = i
                count += 1
            seen[curr] = i
        return count


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        dp = collections.Counter()
        dp[0] = -1

        s = cnt = 0
        right = -1

        for i, n in enumerate(nums):
            s += n
            if s - target in dp:
                left = dp[s - target]
                if right <= left:
                    cnt += 1
                    right = i
            dp[s] = i
        return cnt

class Solution:
    def maxNonOverlapping(self, A: List[int], T: int) -> int:
        N = len(A)
        prefix = [0 for _ in range(N + 1)]
        for i in range(1, N + 1):
            prefix[i] = prefix[i - 1] + A[i - 1]
        seen = set([0])
        res = 0
        for i in range(N):
            curr = prefix[i + 1]
            want = curr - T
            if want in seen:
                res += 1
                seen = set()
            seen.add(curr)
        return res

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        curSum = 0
        sumsSet = {0}
        result = 0
        for x in nums:
            curSum += x
            if (curSum - target) in sumsSet:
                result += 1
                curSum = 0
                sumsSet = {0}
            else:
                sumsSet.add(curSum)
            
        return result

class Solution:
    def maxNonOverlapping(self, A: List[int], target: int) -> int:
        
        # dp[i + 1] = Math.max(dp[i + 1], dp[j] + (sum == target ? 1 : 0));
        # a = [0] * (len(A) + 1)
        # for i in range (len(A)):
        #     sums = 0
        #     for j in reversed(range(i + 1)):
        #         sums += A[j]
        #         a[i + 1] = max(a[i + 1], a[j] + 1 if sums == target else 0)
        # print(a)
        # return a[len(A)]
        
        seen = {0}
        prefix_sum = count = 0
        
        for a in A:
            prefix_sum += a
            if -target + prefix_sum in seen:
                prefix_sum = 0
                count += 1
                seen = set()
            seen.add(prefix_sum)    
            
        return count
            


'''
sliding window approach

initalize left at 0, curr at 0
enumerate through right


'''
class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        n = len(nums)
        presum = [0] * (n + 1)
        for i in range(n):
            presum[i+1] = presum[i] + nums[i]
            
        seen = {0: 0}
        ans = 0
        for i in range(1, n + 1):
            curr = presum[i]
            prev = curr - target
            if prev in seen:
                ans += 1
                seen = {}
            seen[curr] = i
        
        return ans

class Solution:
    
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        if len(nums) == 0:
            return 0
        result = 0
        
        # target = 10
        # [-2,6, 6, 3, 5, 4, 1, 2, 8]
        # [-2,4,10,13,18,22,23,25,33]
        #                         ^
        # seen: [0]
        # result = 2
        
        prefixSums = []
        partial = 0
        for i in range(len(nums)):
            partial += nums[i]
            prefixSums.append(partial)
        
        seen = set([0])
        
        for i in range(len(nums)):
            required = prefixSums[i] - target
            if required in seen:
                result += 1
                seen = set()
            seen.add(prefixSums[i])
            
        return result
        
        


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        store=set([0])
        s=0
        count=0
        
        for i in nums:
            s+=i
            
            if s-target in store:
                count+=1
                store.clear()
                
            store.add(s)
        return count

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        existingSums = set([0])
        prefixsum = 0
        count = 0
        for num in nums:
            prefixsum += num
            
            if prefixsum - target in existingSums:
                count += 1
                existingSums = set([0])
                prefixsum = 0
                
            existingSums.add(prefixsum)
            
            
        return count


class Solution:
    def maxNonOverlapping(self, lis: List[int], tar: int) -> int:
        n = len(lis)
        pre=[0]*(n+1)
        ans=0
        for i in range(n):
            pre[i+1]=pre[i]+lis[i]
        d={0:0}
        for i in range(1,n+1):
            cur = pre[i]
            prev = cur-tar
            if prev in d:
                ans+=1
                d={}
            d[cur]=1
        return ans


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        sums = [0]
        # prefix sum
        for num in nums:
            sums.append(sums[-1] + num)
        
        # two sum
        hashmap = {}
        results = []
        for i, s in enumerate(sums):
            if s in hashmap:
                start = hashmap[s]
                results.append((start, i-1))
            need = s + target
            hashmap[need] = i
        
        prevEnd = -1
        count = 0
        for start, end in results:
            if start > prevEnd:
                count += 1
                prevEnd = end
        return count
            
        


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        seen = {0: -1}
        dp = [0]*(len(nums))
        ans = 0
        for i in range(len(nums)):
            if(i > 0):
                nums[i] += nums[i-1]
                dp[i] = dp[i-1]
            if((nums[i]-target) in seen):
                dp[i]=max(dp[i], dp[seen[nums[i]-target]]+1)
            seen[nums[i]] = i
        return dp[-1]

from collections import defaultdict
class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        
        dp = defaultdict(list)
        res = [(0,-1)]
        tmp_sum = 0
        
        for i, val in enumerate(nums):
            
            tmp_sum += val
            
            if tmp_sum - target == 0 and i > res[-1][1]:
                res.append((0,i))
                tmp_sum = 0
            else:
                if tmp_sum - target in dp and dp[tmp_sum - target][-1] >= res[-1][1] :
                    res.append((0,i))
                    tmp_sum = 0
              
            dp[tmp_sum].append(i)
                    
            # print(dp)
            
                    
        return len(res)-1
                    


class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        res, sm = 0, 0
        hs = set()
        hs.add(0)
        for v in nums:
            sm += v
            if (sm-target) in hs:
                res += 1
                sm = 0
                hs.clear()
                hs.add(0)
            else:
                hs.add(sm)
        return res