algorithm - 使用 Kadane 算法获取最大乘积子数组的范围

Question

应用 Kadane 算法来获得最大乘积子数组似乎很棘手。虽然我能够获得最大乘积，但我并没有真正获得最大乘积子数组的正确范围。

http://www.geeksforgeeks.org/maximum-product-subarray/解释了获得最大产品的方法，但我不知道我们如何获得子数组的范围。

有人可以帮助我理解范围问题吗？这是一个标准的面试问题，我想确保我理解产品案例的逻辑，而不是仅仅说可以修改最大和子数组来回答最大产品子数组案例。

谢谢!!

Answer 1

您提供的链接似乎假定所有元素都是积极的。然而，在我看来，这不是一个安全的假设。我有返回代码以获得最大产品的子数组。我使用了与 Kadane's 中相同的逻辑算法。代码似乎适用于各种输入。如果有问题，请告诉我。

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}