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

Question

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

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

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

谢谢！！

Answer 1

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

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}

Answer 2

def max_subarray(A):
    max_ending_here = max_so_far = 0
    max_start = start = 0
    max_end = end = 0

    # the range is [max_start, max_end)

    for i, x in enumerate(A):
        if max_ending_here + x > 0:
            max_ending_here = max_ending_here + x
            end = i+1
        else:
            max_ending_here = 0
            start = end = i

        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
            max_start = start
            max_end = end

    return (max_start, max_end)

Answer 3

它基本上分为三种情况：

1. 当前数字是 +ve
2. 当前号码是 -ve
3. 当前编号为 0

你需要有两个变量：

• min到目前为止保持最小值

• max迄今为止保持最大值。

现在，case 3 min并且max将被重置为 1。

对于case 1:max将是max * a[i]并且min将是最小的min*a[i]和1.

For case 2:max将是 and 的最大值a[i] * min，1但min值为max * a[i].

下面是代码：

private static int getMaxProduct(int[] a){
    int minCurrent = 1, maxCurrent = 1, max = Integer.MIN_VALUE;
    for (int current : a) {
        if (current > 0) {
            maxCurrent = maxCurrent * current;
            minCurrent = Math.min(minCurrent * current, 1);
        } else if (current == 0) {
            maxCurrent = 1;
            minCurrent = 1;
        } else {
            int x = maxCurrent;
            maxCurrent = Math.max(minCurrent * current, 1);
            minCurrent = x * current;
        }
        if (max < maxCurrent) {
            max = maxCurrent;
        }
    }
    //System.out.println(minCurrent);
    return max;
}