Диапазон подмассива максимального продукта (вариант алгоритма Кадане)

Я пытался получить диапазон максимального продукта подмассива (учусь на собеседования).

Этот вопрос уже задавался здесь (но никаких правильных ответов не было). Получение диапазона максимального подмассива продуктов с использованием алгоритма Каданеса

Этот трюк/алгоритм хорошо объяснен здесь: http://www.geeksforgeeks.org/maximum-product-subarray/

Я могу легко получить максимальный продукт, но после многих попыток все еще не могу понять, как получить диапазон (левый и правый индексы правильно). Кто-нибудь может помочь??

Я вставил свой код, так что вы можете просто скопировать и быстро запустить его.

import java.util.*;

public class ArrayMax {

// maximum product
public static int[] getMaxProduct(int[] list)
{
    int max = 1, min = 1, maxProd = 0;
    int l = 0, left = 0, right = 0;

    for (int i = 0; i < list.length; i++) {

        // positive number!
        if (list[i] > 0) {
            max = max * list[i];
            min = Math.min(1, min * list[i]);
        }
        else if (list[i] == 0) {
            max = 1;    // reset all
            min = 1;
            l = i + 1;
        }
        else {
            // hold the current Max                                  
            int tempMax = max;
                     // need to update left here (but how??)
            max = Math.max(min * list[i], 1); // [-33, 3]
            min = tempMax * list[i];  // update min with prev max

        }

    //  System.out.printf("[%d %d]%n", max, min);       
        if (max >= maxProd) {
            maxProd = max;
            right = i;
            left = l;
        }
    }

    System.out.println("Max: " + maxProd);
    // copy array
    return Arrays.copyOfRange(list, left, right + 1);
}


// prints array
public static void printArray(int[] list) {

    System.out.print("[");
    for (int i = 0; i < list.length; i++) {     
        String sep = (i < list.length - 1) ? "," : "";
        System.out.printf("%d%s", list[i], sep);
    }

    System.out.print("]");
}

public static void main(String[] args) {

    int[][] list = {
        {5, 1, -3, -8},
        {0, 0, -11, -2, -3, 5},
        {2, 1, -2, 9}
    };

    for (int i = 0; i < list.length; i++) {
        int[] res = getMaxProduct(list[i]);

        printArray(list[i]);
        System.out.print(" => ");
        printArray(res);

        System.out.println();
    }
}
}

Вот примеры выходных данных:

Max: 120
[5,1,-3,-8] => [5,1,-3,-8]
Max: 30
[0,0,-11,-2,-3,5] => [-11,-2,-3,5]
Max: 9
[2,1,-2,9] => [2,1,-2,9]

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

Case#2, Max is 30 (correct answer: [-2,-3,5], showing: [-11,-2,-3,5])
Case#3, Max is 9 (correct answer: [9], giving: [2,1,-2,9])

Пожалуйста помоги.


java algorithm kadanes-algorithm sub-array
person Sanjay    schedule 26.05.2014    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Более простой способ - попытаться найти левую позицию/маркер, когда вы вычислили maxProd (в конце). Ваша правая позиция точна, поэтому установите слева направо и разделите maxProd на список [слева], пока не нажмете 1, уменьшая при этом значение влево. Вот когда вы достигли левого.

Следующий код перед возвратом должен решить эту проблему.

int temp = maxProd;
left = right;
while (temp != 1) {
   temp = temp / list[left--];
}
left++;
// copy array
return Arrays.copyOfRange(list, left, right + 1);
person Alif    schedule 26.05.2014
comment
Это прекрасно работает. Спасибо. Есть небольшая проблема (ничего серьезного). Если в начале подмассива есть последовательные 1, например: [1, 1, 5, 6, 9].. это вернет [5,6,9], что все еще правильно :). - person Sanjay; 27.05.2014
comment
@Sanjay это важно, так как [5,6,9] не самый большой подмассив, хотя продукт тот же - person lblasa; 09.02.2018

arrow_upward
1
arrow_downward

Я думаю, вам нужно отслеживать 2 значения для l. Один будет представлять начальный индекс для подмассива чисел, которые умножаются, чтобы получить максимум, а другой будет представлять начальный индекс для подмассива чисел, которые умножаются, чтобы получить минимум.

Однако еще более простой способ — просто подождать, пока вы не найдете максимальный ответ (в maxProd) и его позицию (в правом). В этот момент вы можете затем перебрать массив, умножая элементы списка, пока ваша сумма не достигнет maxProd (начиная справа и повторяя назад). Последний умноженный элемент должен быть началом подмассива.

person Peter de Rivaz    schedule 26.05.2014
comment
Спасибо за решение. Я уже принял другой ответ как выбранный. - person Sanjay; 27.05.2014