用Kadanes算法求最大乘积子阵的值域

Question

应用Kadane算法得到最大乘积子数组是一个棘手的问题。虽然我能够得到最大乘积，但我并没有真正得到最大乘积子数组的正确范围。

有人能帮我了解一下射程问题吗？这是一个标准的面试问题，我想确保我理解了乘积情况的逻辑，而不仅仅是说可以修改最大和子数组来回答最大乘积子数组的情况。

谢谢！！

Answer 1

您提供的链接似乎假设所有元素都是正的。然而，在我看来，这不是一个安全的假设。我有返回代码，以获得最大乘积的子数组。我已经使用了卡丹算法中使用的相同逻辑。代码似乎对我来说适用于各种输入。如果有问题请让我知道。

public static int[] getMaxSubArray(int []arr){

    int maxEndingHere = arr[0], maxSoFar = arr[0], startIndex =0, start =0,end=0;

    for(int i=1;i<arr.length;i++){

        if(maxEndingHere<0){
            maxEndingHere = arr[i];
            startIndex = i;         
        }else{          
            maxEndingHere *= arr[i];
        }           
        if(maxEndingHere>=maxSoFar){
            maxSoFar = maxEndingHere;
            start = startIndex;
            end = i;
        }   
    }       
    if(start<=end)
        return Arrays.copyOfRange(arr, start, end+1);

    return null;
}

1. 示例输入={6,3,-10,0,2}输出={6,3}
2. 示例输入={-2,1,-3,4,-1,2,1,-5,4}输出={4}
3. 示例输入={-1,-2,-9,-6}输出={-1}