Дан массив целых чисел, который может содержать как + ve, так и -ve числа. Я должен максимизировать произведение любых 3 элементов массива. Элементы могут быть несмежными.

Некоторые примеры:

int[] arr = {-5, -7, 4, 2, 1, 9};  // Max Product of 3 numbers = -5 * -7 * 9
int[] arr2 = {4, 5, -19, 3};       // Max Product of 3 numbers = 4 * 5 * 3

Я пытался решить это с помощьюДинамическое программирование, но я не получаю ожидаемого результата. Он возвращает результат, часто включающий одно и то же число дважды в умножении. Итак, для массива -{4, 2, 1, 9}Возвращается -32, который4 * 4 * 2.

Вот мой код:

public static int maxProduct(int[] arr, int count) {
    return maxProduct(arr, 0, arr.length - 1, count);
}

private static int maxProduct(int[] arr, int fromIndex, int toIndex, int count) {

    if (count == 1) {
        return maximum(arr, fromIndex, toIndex);
    } else if (toIndex - fromIndex + 1 < count) {
        return 1;
    } else {
        return MathUtil.max(maxProduct(arr, fromIndex, toIndex - 1, count - 1) * arr[toIndex - 1], 
                            maxProduct(arr, fromIndex, toIndex - 1, count));
    }
}

MathUtil.max(int a, int b) это метод, который дает максимумa а такжеb.Два значения, которые я передаюmax Метод есть:maxProduct, когда мы рассматриваем последний элемент как часть продукта.maxProductкогда мы не рассматриваем это как часть продукта.count содержит номер элемента, который мы хотим рассмотреть. Вот3.Заcount == 1, мы должны найти максимум 1 элемент из массива. Это означает, что мы должны использовать максимальный элемент массива.ЕслиtoIndex - fromIndex + 1 < countозначает, что в массиве недостаточно элементов между этими индексами.

У меня есть интуиция, что первыйif состояние является одной из причин отказа. Потому что он рассматривает только максимальный элемент из массива, в то время как максимальный продукт также может содержать отрицательные числа. Но я не знаю, как позаботиться об этом.

Причина, по которой я использую динамическое программирование, заключается в том, что я могу обобщить это решение для работы с любым значениемcount, Конечно, если у кого-то есть лучший подход, даже дляcount = 3Я приветствую предложение (я хотел бы избежать сортировки массива, так как это будет другойO(nlogn) как минимум).