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

class Solution {
public:

    bool check(stack<int>& p,int& maxi)
    {
        int sum=0;
        stack<int> temp;
        int i=1;
        while(!p.empty())
        {
            int top = p.top();
            temp.push(top);
            p.pop();
            sum+=i*top;
            i++;
        }
        if(sum > maxi)
        {
            maxi=sum;
            while(!temp.empty())
            {
                p.push(temp.top());
                temp.pop();
            }
            return true;
        }
        else
            return false;
    }

    // int solve(vector<int>& arr,int index)
    // {
    //     if(index==arr.size())
    //         return INT_MAX;
        
    //     int incl = index
    // }

    int maxSatisfaction(vector<int>& satisfaction) {
        // return solve(satisfaction,0);
        vector<int> pos,neg;
        for(int i=0;i<satisfaction.size();i++)
        {
            if(satisfaction[i]<0)
                neg.push_back(satisfaction[i]);
            else
                pos.push_back(satisfaction[i]);
        }

        int maxi=0;

        if(neg.size()==0)
        {
            sort(pos.begin(),pos.end());
            for(int i=1;i<=pos.size();i++)
            {
                maxi += i*pos[i-1];
            }
            return maxi;
        }
        else if(pos.size()==0)
            return 0;
        else{
            sort(pos.begin(),pos.end());
            sort(neg.begin(),neg.end());
            stack<int> p;
            for(int i=pos.size()-1;i>=0;i--)
                p.push(pos[i]);
            for(int i=1;i<=pos.size();i++)
            {
                maxi += i*pos[i-1];
            }
            for(int i=neg.size()-1;i>=0;i--)
            {
                p.push(neg[i]);
                if(check(p,maxi))
                    continue;
                else
                    break;
            }
            return maxi;
        }
        
    }
};
22100