<p>A chef has collected data on the <code>satisfaction</code> level of his <code>n</code> dishes. Chef can cook any dish in 1 unit of time.</p>

<p><strong>Like-time coefficient</strong> of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. <code>time[i] * satisfaction[i]</code>.</p>

<p>Return the maximum sum of <strong>like-time coefficient </strong>that the chef can obtain after preparing some amount of dishes.</p>

<p>Dishes can be prepared in <strong>any </strong>order and the chef can discard some dishes to get this maximum value.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> satisfaction = [-1,-8,0,5,-9]
<strong>Output:</strong> 14
<strong>Explanation:</strong> After Removing the second and last dish, the maximum total <strong>like-time coefficient</strong> will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> satisfaction = [4,3,2]
<strong>Output:</strong> 20
<strong>Explanation:</strong> Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> satisfaction = [-1,-4,-5]
<strong>Output:</strong> 0
<strong>Explanation:</strong> People do not like the dishes. No dish is prepared.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == satisfaction.length</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>-1000 &lt;= satisfaction[i] &lt;= 1000</code></li>
</ul>

"""
Problem: https://leetcode.com/problems/reducing-dishes/description/?envType=problem-list-v2&envId=50vif4uc
Difficulty: hard
Solved: false
"""

from typing import List


class Solution:
    def __init__(self) -> None:
        self.dp = []
        self.dishes = []
        self.N = -1

    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        # Primeiro ordenamos a lista de pratos para que possamos sempre pegar os prator com o melhor valor primeiro.
        satisfaction.sort()
        self.N = len(satisfaction)

        # Aqui populamos a tabela DP que contém a relação Pratos X Tempo do Preparo
        # Todos os valores são iniciados como 0 pois é o caso base. Se não há pratos que satisfaçam os clientes, nenhum prato é preparado.
        self.dp = [[0] * (self.N + 1) for _ in range(self.N + 1)]

        # O processo de decisão aqui se baseia em iterar em cada prato *i* e avaliar entre os tempos de preparo disponíveis
        # qual é a melhor ação a ser tomada de acordo com o total acumulado até o momento.
        # Em cada iteração podemos tomar duas decisões:
        #   - 1) Cozinhar o prato i, retornando o resultado (valor[i] * time) + opt(i+1, time+1)
        #   - 2) Se não cozinhar o prato i, passamos ao resultado do próximo prato no tempo atual: opt(i+1, time)

        # Começamos iterando pelos pratos com o maior valor de satisfação
        for i in range(self.N - 1, -1, -1):
            for time in range(self.N):
                cooking = None
                not_cooking = None

                # Se não decirmos cozinhar o prato, buscamos apenas o resultado do próximo item ou retornamos 0 que é o caso base.
                if (i + 1) < self.N:
                    not_cooking = self.dp[i + 1][time]
                else:
                    not_cooking = 0

                # Conzinhando o prato, somamos o coeficiente obtido com o maxímo valor calculado para o resto dos pratos até o momento.
                if (i + 1) < self.N:
                    cooking = (satisfaction[i] * (time + 1)) + (
                        self.dp[i + 1][time + 1]
                    )
                else:
                    cooking = satisfaction[i] * (time + 1)

                # O valor a ser colocado na tabela é o maior entre os dois calculados.
                self.dp[i][time] = max(cooking, not_cooking)

        return self.dp[0][0]

22400