El «coeficiente like-time» de un plato se define como el tiempo en que termina de preparar el plato (incluyendo el tiempo de las preparaciones anteriores) multiplicado por el nivel de satisfacción de ese plato, es decir, tiempo\[i\] \* satisfaccion\[i\].

Devolución de la suma máxima del «coeficiente like-time» que puede obtener el chef después de preparar una cierta cantidad de platos.

Puedes organizar el orden de preparación en **cualquier** orden, y también puedes elegir omitir algunos platos para obtener una suma mayor.

Ejemplo 1:

Entrada: satisfaccion = [-1,-8,0,5,-9]

Salida: 14

Explicación: Al omitir el segundo y el último plato, la suma máxima del coeficiente like-time es (-1*1 + 0*2 + 5*3 = 14). Cada plato requiere 1 unidad de tiempo para completarse.

Ejemplo 2:

Entrada: satisfaccion = [4,3,2]

Salida: 20

Explicación: Se pueden preparar los platos en cualquier orden (2*1 + 3*2 + 4*3 = 20)

Ejemplo 3:

Entrada: satisfaccion = [-1,-4,-5]

Salida: 0

Explicación: A nadie le gustan estos platos, por lo que no preparar ningún plato se obtiene la suma máxima del coeficiente like-time.

Enfoque de solución:

Para resolver este problema utilizando un algoritmo greedy, primero podemos ordenar el array. Una vez ordenado, podemos iterar desde el final hacia el principio:

Tomando el Ejemplo 1 como referencia: satisfaccion = [-1,-8,0,5,-9], después de ordenar el array se convierte en [-9,-8,-1,0,5], e iterando desde el final hacia el principio, establecemos una variable para almacenar su suma:

int T=0;

Primera iteración: T=5

Segunda iteración: T=(5)+(5+0)

Tercera iteración: T=(5)+(5+0)+(5+0-1)

Cuarta iteración: (5)+(5+0)+(5+0-1)+(5+0-1-9) < tercera

Dado que el array está ordenado de menor a mayor, conntinuar hacia atrás solo reducirá los valores. Por lo tanto, después de la tercera iteración, los valores no serán mayores que en la tercera, y podemos finalizar el ciclo, devolviendo el valor máximo de T.

Implementación del código:

class Solucion {
    public int maximaSatisfaccion(int[] satisfaccion) {
        // Ordenar el array
        Arrays.sort(satisfaccion);
        // max registra el valor anterior de T
        int max = 0;
        int T = 0;
        for(int x = satisfaccion.length-1; x >= 0; x--) {
            // Ciclo for desde el final hacia el índice actual
            for(int y = satisfaccion.length-1; y >= x; y--) {
                // T suma desde el final hacia adelante
                T += satisfaccion[y];
            }
            // Si T < max, significa que el valor anterior de T ya alcanzó el máximo
            // y los siguientes valores solo serán menores, así que salimos del ciclo
            if(max >= T) break;
            // De lo contrario, asignamos max = T
            else max = T;
        }
        return max;
    }
}

Sin embargo, esta implementación no es la más óptima. Podemos optimizarla aún más.

Basándonos en el ejemplo anterior, podemos deducir que cada ciclo itera sobre todos los elementos previamente procesados. ¿Podemos pensar en ello de manera diferente? Cada vez que se introduce una nueva variable, ¿podemos sumarla al valor máximo actual?

Por ejemplo, en el Ejemplo 1:

int T=0, max=0;

Primera iteración: T=5 max+T=5

Segunda iteración: T=5+0 max+T=10

Tercera iteración: T=5+0-1 max+T=14

Cuarta iteración: T=5+0-1-9 T<0, entonces max+T solo será menor, por lo que el valor de max en la tercera iteración es el máximo, lo devolvemos.

Implementación del código optimizado:

class Solucion {
    public int maximaSatisfaccion(int[] satisfaccion) {
        // Ordenar el array
        Arrays.sort(satisfaccion);
        int max = 0;
        int T = 0;
        // Iterar desde el final hacia el principio
        for(int x = satisfaccion.length-1; x >= 0; x--) {
            // Sumar el elemento correspondiente a T
            // Si T > 0, sumamos T a max
            // Si T es menor que cero, significa que max ha alcanzado su valor máximo
            // Devolvemos max
            T += satisfaccion[x];
            if(T < 0) break;
            max += T;
        }
        return max;
    }
}