package leetcode;

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

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

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -268,32 +268,1036 @@
     
-// TODO%0A        return 0
+return maxNonOverlapping(nums, target, 0, nums%5B0%5D, new HashMap%3C%3E());%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 + sum;%0A        if (memo.containsKey(key)) %7B%0A            return memo.get(key);%0A        %7D%0A        int max = 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  
@@ -1728,20 +1728,334 @@
 , 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%0A
     %7D%0A%7D%0A

Update problem 1546