Получение диапазона максимального массива продукта с использованием алгоритма Каданеса

Question

Применение алгоритма Кадане для получения максимального массива продукта кажется сложным. Несмотря на то, что я могу получить максимальный продукт, я не получаю правильный диапазон подмассива максимального продукта.

http://www.geeksforgeeks.org/maximum-product-subarray/ объясняет, как получить максимальный продукт, но я не понимаю, как мы можем получить диапазон подмассива.

Может кто-нибудь помочь мне понять проблему дальности? Это стандартный вопрос интервью, и я хочу убедиться, что я понимаю логику для случая продукта, вместо того, чтобы просто сказать, что подмассив max sum может быть изменен, чтобы ответить на случай подмассива max product.

Спасибо!!

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}

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 3min а также max будет сброшен на 1.

За case 1: max будет max * a[i] а также min будет минимум min*a[i] а также 1.

За case 2: max будет максимум 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;
}