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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Range queries

Greedy algorithms

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):
			if cumsum[i + 1] - target in d:
				temp.append((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:
		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)
		seen = set([])
		for c in csum[:]:
			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 = {}
			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):
			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, target) -> int:
		hashMap = {0: -1}
		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:
		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:
		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 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)
		ans = 0
		seen = {}
		for (i, v) in enumerate(sums):
			if v - target in seen:
				ans += 1
				seen = {}
			seen[v] = i
		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


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)
		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


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, 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
		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:
		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
		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
		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
		return dp[-1]


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:
		pref = [0] * (len(nums) + 1)
		for i in range(len(nums)):
			pref[i + 1] = pref[i] + nums[i]
		d = {}
		ans = 0
		for i in range(len(pref)):
			if pref[i] - target in d:
				ans += 1
				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:
		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
				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:
		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
			if t in mem:
				dp[i] = max(dp[i], dp[mem[t]] + 1)
			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 prefix - target in cnt:
				ans += 1
				cnt = collections.Counter()
			cnt[prefix] += 1
		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:
		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
		return count


class Solution:

	def maxNonOverlapping(self, nums: List[int], target: int) -> int:
		n = len(nums)
		prefix_sum = [0] * n
		lookup = {}
		dp = [0] * n
		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]


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])
		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


from collections import defaultdict

class Solution:

	def maxNonOverlapping(self, nums: List[int], target: int) -> int:
		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, 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


class Solution:

	def maxNonOverlapping(self, nums: List[int], target: int) -> int:
		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:
				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:
				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)
			elif 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
		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:
		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:
		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], target: int) -> int:
		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


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]
		for num in nums:
			sums.append(sums[-1] + num)
		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


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
			elif 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)
		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