1402. Reducing Dishes Hard

1/**
2 * [1402] Reducing Dishes
3 *
4 * A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.
5 * Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i] * satisfaction[i].
6 * Return the maximum sum of like-time coefficient that the chef can obtain after dishes preparation.
7 * Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.
8 *  
9 * Example 1:
10 * 
11 * Input: satisfaction = [-1,-8,0,5,-9]
12 * Output: 14
13 * Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
14 * Each dish is prepared in one unit of time.
15 * Example 2:
16 * 
17 * Input: satisfaction = [4,3,2]
18 * Output: 20
19 * Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)
20 * 
21 * Example 3:
22 * 
23 * Input: satisfaction = [-1,-4,-5]
24 * Output: 0
25 * Explanation: People do not like the dishes. No dish is prepared.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	n == satisfaction.length
31 * 	1 <= n <= 500
32 * 	-1000 <= satisfaction[i] <= 1000
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/reducing-dishes/
38// discuss: https://leetcode.com/problems/reducing-dishes/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    pub fn max_satisfaction(satisfaction: Vec<i32>) -> i32 {
44        0
45    }
46}
47
48// submission codes end
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn test_1402() {
56    }
57}
58