<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>

# my current idea: 
# Start from the last, the -ve at last is useless, discard directly
# Until we meet the first +ve. Then, we start our window
# along the journey, if we meet +ve, just put in; if -ve, then compare whether it has advantage in putting it in
# If yes then do, others discard, proceed to the prev item

# Note that here dishes can be prepared in ANY ORDER! Then confirm should arrange larger dishes to later
# And only accept negative values until the FIRST ONE in which the harm outweights the benefit

from collections import deque

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:    
        satisfaction.sort()
        if satisfaction[-1] < 0:
            return 0
        print(satisfaction)

        ptr = len(satisfaction) - 1
        window = deque([])
        while ptr >= 0 and satisfaction[ptr] >= 0:
            # then always beneficial, just take in
            window.appendleft(satisfaction[ptr])
            currScore = sum((i+1) * window[i] for i in range(len(window))) # Err, just try to get the score first
            # print(f"Current window is {window}, currScore is {currScore}, just after ptr {ptr}")
            ptr -= 1

        # if there are still -ve values, then need to probe
        # print("into negative")
        beneficial = True
        while ptr >= 0 and beneficial:
            windowTemp = window.copy()
            windowTemp.appendleft(satisfaction[ptr])
            planA = sum((i+1) * windowTemp[i] for i in range(len(windowTemp)))
            planB = currScore

            if planA > planB: # then still beneficial to take the -ve value in
                window.appendleft(satisfaction[ptr])
                currScore = planA
            else:
                beneficial = False
            # print(f"Current window is {window}, currScore is {currScore}, just after ptr {ptr}")
            ptr -= 1

        return currScore


        




    # def maxSatisfaction(self, satisfaction: List[int]) -> int:    
    #     ptr = len(satisfaction) - 1
    #     while ptr >= 0 and satisfaction[ptr] < 0:
    #         ptr -= 1
    #     if ptr < 0:
    #         # then no positive dish whatsoever, return 0
    #         return 0

    #     window = deque([satisfaction[ptr]])
    #     currScore = 1 * satisfaction[ptr]
    #     ptr -= 1 # exclude double-count of 1st item
    #     print(f"At start, window {window}, currScore {currScore}, ptr {ptr}")

    #     while ptr >= 0:
    #         if satisfaction[ptr] >= 0:
    #             window.appendleft(satisfaction[ptr])
    #             currScore = sum((i+1) * window[i] for i in range(len(window))) # Err, just try to get the score first
    #         else:
    #             windowTemp = window.copy()
    #             windowTemp.appendleft(satisfaction[ptr])
    #             planA = sum((i+1) * windowTemp[i] for i in range(len(windowTemp)))
    #             planB = currScore

    #             if planA > planB:
    #                 window.appendleft(satisfaction[ptr])
    #                 currScore = planA
    #             # else just do nothning

    #         print(f"Current window {window}, current sum {currScore}, this is just after ptr {ptr}")
    #         ptr -= 1

    #     return currScore



        
16700