題目連結(jié)：
題目意譯：
一位主廚蒐集了一些他對(duì)於 n 道料理的滿意程度之?dāng)?shù)據(jù)。該主廚在一單位時(shí)間可以做出任意一道料理。
一道料理的「好時(shí)」係數(shù)（原文：Like-time Coefficient）定義為做出該料理的時(shí)間（包含前面的料理）乘以其滿意程度，即 time[i] × satisfaction[i]。
回傳藉由準(zhǔn)備若干道料理後，該主廚可以達(dá)到的最大好時(shí)係數(shù)之總和值。
這些料理可以按任意順序製作，也可以捨棄若干道料理來(lái)使主廚得到這個(gè)最大值。
限制：
n == satisfaction.length
1 ≦ n ≦ 500
-1000 ≦ satisfaction[i] ≦ 1000
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： satisfaction = [-1,-8,0,5,-9]
輸出： 14
解釋： 在移除第二道與最後一道料理之後，最大好時(shí)係數(shù)總和將等於 (-1×1 + 0×2 + 5×3 = 14)。
每一道料理各自都會(huì)在一單位時(shí)間內(nèi)完成。
範(fàn)例 2：
輸入： satisfaction = [4,3,2]
輸出： 20
解釋： 這些料理可以按任意順序製作，(2×1 + 3×2 + 4×3 = 20)
範(fàn)例 3：
輸入： satisfaction = [-1,-4,-5]
輸出： 0
解釋： 人們不喜歡這些料理。主廚將不準(zhǔn)備任何一道料理。
解題思維：
可以看到最佳解中每一道料理的滿意程度必定將會(huì)是以非嚴(yán)格遞增之順序排列，即越早做的滿意程度越低、越晚做的滿意程度越高。因?yàn)闀r(shí)間的係數(shù)是固定的，而為了最大化總和就只能將滿意程度大的配上時(shí)間係數(shù)大的。
因此我們可以先將 satisfaction 中的數(shù)字由小排到大。
接著我們可以從範(fàn)例測(cè)資 1 看到最佳解不一定只有挑出滿意程度是正的那些料理，因?yàn)橛袔讉€(gè)小的負(fù)滿意程度的料理存在可以把正滿意程度大之時(shí)間係數(shù)變大，而這可能反而會(huì)比較好。
所以我們先當(dāng)作所有料理都要做，因而算出一個(gè)包含著所有料理的好時(shí)係數(shù)總和 LT。此時(shí)在過(guò)程中順便求出一個(gè)所有料理滿意程度之總和 S（等下會(huì)用到）。
可以看到在「必定要做恰好 n 道料理」（即全部的料理）的情況下，最佳解就是 LT。那 n - 1 道呢？我們可以移除哪一道料理？
答案很簡(jiǎn)單，移除最一開(kāi)始做的那一道料理即可，因?yàn)槠錆M意程度是最低的。因此最佳解為 LT - S（因?yàn)樯倭艘坏懒侠恚@意味著每一道料理的時(shí)間係數(shù)將都統(tǒng)一減去 1，而總體被減去的總和恰好為 S）。
此時(shí)將 S 減去第一道料理的滿意程度，我們便得到在「必定要做恰好 n - 1 道料理」的情況下的最佳解以及這 n - 1 道料理的滿意程度之總和。
因此我們可以重複上述的論述直到把所有料理的移除光光為止。
而所求的「真」最佳解即是
「必定要做恰好 n 道料理」的最佳解、
「必定要做恰好 n - 1 道料理」的最佳解、
……
「必定要做恰好 1 道料理」的最佳解、
「必定要做恰好 0 道料理」的最佳解（此值必為 0）。
上述各自的最佳解中的最大值。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
