Why does memoized code fails while recursive approach works for maximum length of subarray with positive product?

Question

I am trying to solve the problem:

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.

Example 2:

Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

My Solution:

class Solution {
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        Map<String,Integer> map = new HashMap<>();
        int v1 = helper(nums,n,1,0,map);
        if(v1 == -1)
            return 0;
        
        return v1;
    }
    
    public int helper(int[] nums,int n,long product,int length,Map<String,Integer> map) {
        if(n == 0){
            if(product>0)
                return length;
            
            return -1;
        }
        
        String str = "" + n + "-" + product+"-"+length;
        
        if(map.get(str) != null){
            if(product > 0)
                return map.get(str);
        }
        
        if(nums[n-1] == 0){
            int v1 = helper(nums,n-1,1,0,map);
            
            if(product <= 0)
                length = 0;
            
            int v2 = Math.max(length,v1);
            
            map.put(str,v2);
            return v2;            
        }
        else{
            int v4 = helper(nums,n-1,product*nums[n-1],length+1,map);
            int v3 = helper(nums,n-1,nums[n-1],1,map);
        
            if(product <= 0)
                length = 0;
            
            int v5 = Math.max(length,Math.max(v3,v4));
           
            map.put(str,v5);
            return v5;
        }
    }
}

Fails At:

Input: 
[70,-18,75,-72,-69,-84,64,-65,0,-82,62,54,-63,-85,53,-60,-59,29,32,59,-54,-29,-45,0,-10,22,42,-37,-16,0,-7,-76,-34,37,-10,2,-59,-24,85,45,-81,56,86]
Output: 13
Expected: 14

I searched for the solution but everyone is working directly on tabulation rather than memoization

Answer 1

First off all your problem is not with your memoization you could simply comment out parts related to memozation and you would still get the wrong answer. Your problem is stack overflow, simply multiplying numbers [-82,62,54,-63,-85,53,-60,-59,29,32,59,-54,-29,-45] exceeds maximum long value, and you would get a wrong answer, becuase you store multiplication of these numbers in a long value. To solve this problem I eliminate the magnitude of numbers and just using their signs. I've also splited my array to smaller arrays containning non-zero values using the function splitToZero which you can see in my code.

But your memozation is not correct either. I've implemented two methods for helper, show casing the improvemnt from memotazation, which you could see that it would be about 20 times faster if we use memotazation comparing to when we dont use that(I've just call the methods 1000 times to have a sensable time for comparision).

public int getMaxLen(int[] nums) {
    List<int[]> ints = splitToZero(nums);
    timeComparison(ints);
    int max = 0;
    for (int[] arr : ints) {
        Map<int[], Integer> map = new HashMap<>();
        int len = arr.length;
        int v1 = helperWithMemotazation(arr, len, 1, 0, map);
        if (v1 > max)
            max = v1;
    }
    return max;
}

private void timeComparison(List<int[]> ints) {
    long startTimeMillis = System.currentTimeMillis();
    for (int i = 0; i < 1000; i++)
        for (int[] arr : ints) {
            Map<int[], Integer> map = new HashMap<>();
            int len = arr.length;
            helperWithMemotazation(arr, len, 1, 0, map);
        }
    long endTimeMillis = System.currentTimeMillis();
    System.out.println(endTimeMillis - startTimeMillis);

    startTimeMillis = System.currentTimeMillis();
    for (int i = 0; i < 1000; i++)
        for (int[] arr : ints) {
            int len = arr.length;
            helperWithoutMemotazation(arr, len, 1, 0);
        }
    endTimeMillis = System.currentTimeMillis();
    System.out.println(endTimeMillis - startTimeMillis);
}

public List<int[]> splitToZero(int[] nums) {
    List<int[]> result = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    for (int num : nums) {
        if (num != 0) {
            list.add(num);
        } else {
            if (list.size() > 0) {
                int[] temp = new int[list.size()];
                for (int j = 0; j < list.size(); j++)
                    temp[j] = list.get(j) / Math.abs(list.get(j));
                result.add(temp);
                list.clear();
            }
        }
    }
    if (list.size() > 0) {
        int[] temp = new int[list.size()];
        for (int j = 0; j < list.size(); j++)
            temp[j] = list.get(j) / Math.abs(list.get(j));
        result.add(temp);
    }
    return result;
}

public int helperWithMemotazation(int[] nums, int n, long product, int length, Map<int[], Integer> map) {
    if (n == 0) {
        if (product > 0)
            return length;
        return -1;
    }
    if (map.containsKey(nums)) {
        return map.get(nums);
    }
    int v4 = helperWithMemotazation(nums, n - 1, product * nums[n - 1], length + 1, map);
    int v3 = helperWithMemotazation(nums, n - 1, nums[n - 1], 1, map);
    if (product <= 0)
        length = 0;
    int v5 = Math.max(length, Math.max(v3, v4));
    map.put(nums, v5);
    return v5;
}

public int helperWithoutMemotazation(int[] nums, int n, long product, int length) {
    if (n == 0) {
        if (product > 0)
            return length;
        return -1;
    }
    int v4 = helperWithoutMemotazation(nums, n - 1, product * nums[n - 1], length + 1);
    int v3 = helperWithoutMemotazation(nums, n - 1, nums[n - 1], 1);
    if (product <= 0)
        length = 0;
    return Math.max(length, Math.max(v3, v4));
}