package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/
 */
public class Problem1546 {
    public int maxNonOverlapping(int[] nums, int target) {
        return maxNonOverlapping(nums, target, 0, nums[0], new HashMap<>());
    }

    private static int maxNonOverlapping(int[] nums, int target, int index, int sum,
                                         Map<String, Integer> memo) {
        if (index == nums.length) {
            return 0;
        }
        String key = index + "," + sum;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        int max = 0;
        int nextVal = index + 1 < nums.length ? nums[index + 1] : 0;
        if (sum == target) {
            int a = maxNonOverlapping(nums, target, index + 1, 0, memo) + 1;
            int b = maxNonOverlapping(nums, target, index + 1, nextVal, memo) + 1;
            max = Math.max(max, Math.max(a, b));
        } else {
            int a = maxNonOverlapping(nums, target, index + 1, 0, memo);
            int b = maxNonOverlapping(nums, target, index + 1, sum + nextVal, memo);
            max = Math.max(max, Math.max(a, b));
        }
        memo.put(key, max);
        return max;
    }

    public static void main(String[] args) {
        Problem1546 prob = new Problem1546();
        System.out.println(prob.maxNonOverlapping(new int[]{1,1,1,1,1}, 2)); // 2
        System.out.println(prob.maxNonOverlapping(new int[]{-1,3,5,1,4,2,-9}, 6)); // 2
        System.out.println(prob.maxNonOverlapping(new int[]{-2,6,6,3,5,4,1,2,8}, 10)); // 3
        System.out.println(prob.maxNonOverlapping(new int[]{0,0,0}, 0)); // 3
        System.out.println(prob.maxNonOverlapping(new int[]{1,1,1,1,1,3,0,8,24,5,3,23,98,5,38,5,2,45,4,5,9,9,17,5,2,25,9,23}, 9)); // 4
        System.out.println(prob.maxNonOverlapping(new int[]{4,5,9,9,5,2,9}, 9)); // 4
        System.out.println(prob.maxNonOverlapping(new int[]{1,1,5,2,4,5,1,9,9,9}, 9)); // 5
    }
}

@@ -33,19 +33,19 @@
 til.Hash
-Map
+Set
 ;%0Aimport
@@ -55,19 +55,19 @@
 va.util.
-Map
+Set
 ;%0A%0A/**%0A 
@@ -268,345 +268,121 @@
     
-return maxNonOverlapping(nums, target, 0, nums%5B0%5D, new HashMap%3C%3E())
+int answer = 0
 ;%0A    
-%7D%0A%0A
     
-private static int maxNonOverlapping(int%5B%5D nums, int target, int index, int sum,%0A                                         Map%3CString, Integer%3E memo) %7B%0A        if (index == nums.length) %7B%0A            return 0;%0A        %7D%0A        String key = index + %22,%22 + s
+int prefixSum = 0;%0A        Set%3CInteger%3E set = new HashSet%3C%3E();%0A        set.add(prefixS
 um
+)
 ;%0A  
@@ -391,1442 +391,267 @@
     
-if (memo.containsKey(key)) %7B%0A            return memo.get(key);%0A        %7D%0A        
+for (
 int 
-max
+i
  = 0;
-%0A        int nextVal = index + 1 %3C nums.length ? nums%5Bindex + 1%5D : 0;%0A        if (sum == target) %7B%0A            int a = maxNonOverlapping(nums, target, index + 1, 0, memo) + 1;%0A            int b = maxNonOverlapping(nums, target, index + 1, nextVal, memo) + 1;%0A            max = Math.max(max, Math.max(a, b));%0A        %7D else %7B%0A            int a = maxNonOverlapping(nums, target, index + 1, 0, memo);%0A            int b = maxNonOverlapping(nums, target, index + 1, sum + nextVal, memo);%0A            max = Math.max(max, Math.max(a, b));%0A        %7D%0A        memo.put(key, max);%0A        return max;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1546 prob = new Problem1546();%0A        System.out.println(prob.maxNonOverlapping(new int%5B%5D%7B1,1,1,1,1%7D, 2)); // 2%0A        System.out.println(prob.maxNonOverlapping(new int%5B%5D%7B-1,3,5,1,4,2,-9%7D, 6)); // 2%0A        System.out.println(prob.maxNonOverlapping(new int%5B%5D%7B-2,6,6,3,5,4,1,2,8%7D, 10)); // 3%0A        System.out.println(prob.maxNonOverlapping(new int%5B%5D%7B0,0,0%7D, 0)); // 3%0A        System.out.println(prob.maxNonOverlapping(new int%5B%5D%7B1,1,1,1,1,3,0,8,24,5,3,23,98,5,38,5,2,45,4,5,9,9,17,5,2,25,9,23%7D, 9)); // 4%0A        System.out.println(prob.maxNonOverlapping(new int%5B%5D%7B4,5,9,9,5,2,9%7D, 9)); // 4%0A        System.out.println(prob.maxNonOverlapping(new int%5B%5D%7B1,1,5,2,4,5,1,9,9,9%7D, 9)); // 5
+ i %3C nums.length; i++) %7B%0A            prefixSum += nums%5Bi%5D;%0A            if (set.contains(prefixSum - target)) %7B%0A                answer++;%0A                set.clear();%0A            %7D%0A            set.add(prefixSum);%0A        %7D%0A        return answer;
 %0A   

Solve problem 1546