为什么记忆代码会失败，而递归方法适用于具有正积的子数组的最大长度？

Question

我正在尝试解决这个问题：

给定一个整数数组 nums，找到所有元素的乘积为正的子数组的最大长度。

数组的子数组是从该数组中取出的零个或多个值的连续序列。

返回具有正积的子数组的最大长度。

示例 1：

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

示例 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.

示例 3：

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

我的解决方案：

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

失败于：

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

我搜索了解决方案，但每个人都直接进行制表而不是记忆

Answer 1

首先，您的所有问题都不在于记忆，您可以简单地注释掉与记忆相关的部分，但您仍然会得到错误的答案。您的问题是堆栈溢出，只需将数字相乘[-82,62,54,-63,-85,53,-60,-59,29,32,59,-54, -29,-45] 超过了最大长值，您会得到错误的答案，因为您将这些数字的乘法存储在长值中。为了解决这个问题，我消除了数字的大小，只使用它们的符号。我还使用函数 splitToZero 将数组拆分为包含非零值的较小数组，您可以在我的代码中看到该函数。

但你的记忆也不正确。我已经为 helper 实现了两种方法，展示了 memotazation 的改进，您可以看到，如果我们使用 memotazation，与不使用它时相比，速度会快大约 20 倍（我已经只需调用这些方法 1000 次即可获得合理的比较时间）。

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