Encontre o produto máximo de 3 números em uma matriz

Dada uma matriz de números inteiros, que pode conter os números + ve e -ve. Eu tenho que maximizar o produto de quaisquer 3 elementos da matriz. Os elementos podem ser não contíguos.

Alguns exemplos:

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

Eu tentei resolvê-lo usandoProgramaçao dinamica, mas não estou obtendo o resultado esperado. Ele está retornando o resultado geralmente envolvendo o mesmo número duas vezes na multiplicação. Então, para a matriz -{4, 2, 1, 9}, está retornando -32, qual é4 * 4 * 2.

Aqui está o meu código:

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) é um método que fornece o máximo dea eb.Os dois valores que eu passo paramax método existem:maxProduct, quando consideramos o último elemento como parte do produto.maxProduct, quando não o consideramos parte do produto.count contém o número de elemento que queremos considerar. Aqui3.Paracount == 1, temos que encontrar no máximo 1 elemento da matriz. Isso significa que temos que usar o elemento máximo da matriz.E setoIndex - fromIndex + 1 < count, significa que não há elementos suficientes na matriz entre esses índices.

Eu tenho uma intuição de que, o primeiroif condição é uma das razões da falha. Porque, ele está considerando apenas o elemento máximo de uma matriz, enquanto o produto máximo também pode incluir números negativos. Mas eu não sei como cuidar disso.

O motivo pelo qual estou usando a Programação dinâmica é que posso generalizar essa solução para trabalhar com qualquer valor decount. Obviamente, se alguém tiver uma abordagem melhor, mesmo paracount = 3, Agradeço a sugestão (gostaria de evitar a classificação da matriz, pois essa será outraO(nlogn) pelo menos).