1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/**
 * Find the maximum sum of like-time coefficients.
 * Greedy Approach with Sorting.
 *
 * @param {number[]} satisfaction - Array of satisfaction levels
 * @return {number} - Maximum sum of like-time coefficients
 */
function maxSatisfaction(satisfaction) {
  // Sort the satisfaction array in ascending order
  satisfaction.sort((a, b) => a - b);
 
  let total = 0;  // Sum of satisfaction levels
  let result = 0;  // Maximum sum of like-time coefficients
 
  // Iterate through the sorted array from right to left
  for (let i = satisfaction.length - 1; i >= 0; i--) {
    // Add the current satisfaction level to total
    total += satisfaction[i];
 
    // Add total to result
    result += total;
 
    // If total becomes negative, it's better to stop including dishes
    if (total < 0) {
      result -= total;
      break;
    }
  }
 
  return result;
}
 
/**
 * Find the maximum sum of like-time coefficients.
 * Dynamic Programming approach.
 *
 * @param {number[]} satisfaction - Array of satisfaction levels
 * @return {number} - Maximum sum of like-time coefficients
 */
function maxSatisfactionDP(satisfaction) {
  // Sort the satisfaction array in ascending order
  satisfaction.sort((a, b) => a - b);
 
  const n = satisfaction.length;
 
  // Initialize DP array
  const dp = Array(n + 1).fill().map(() => Array(n + 1).fill(0));
 
  // Fill DP array
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= i; j++) {
      // Include the dish
      const include = dp[i - 1][j - 1] + satisfaction[i - 1] * j;
 
      // Exclude the dish
      const exclude = dp[i - 1][j];
 
      // Take the maximum
      dp[i][j] = Math.max(include, exclude);
    }
  }
 
  // Find the maximum value in dp[n][j] for all j from 0 to n
  let result = 0;
  for (let j = 0; j <= n; j++) {
    result = Math.max(result, dp[n][j]);
  }
 
  return result;
}
 
/**
 * Find the maximum sum of like-time coefficients.
 * Optimized Greedy Approach.
 *
 * @param {number[]} satisfaction - Array of satisfaction levels
 * @return {number} - Maximum sum of like-time coefficients
 */
function maxSatisfactionOptimized(satisfaction) {
  // Sort the satisfaction array in ascending order
  satisfaction.sort((a, b) => a - b);
 
  let total = 0;  // Sum of satisfaction levels
  let result = 0;  // Maximum sum of like-time coefficients
 
  // Iterate through the sorted array from right to left
  for (let i = satisfaction.length - 1; i >= 0; i--) {
    // Add the current satisfaction level to total
    total += satisfaction[i];
 
    // If total becomes negative, it's better to stop including dishes
    if (total <= 0) {
      break;
    }
 
    // Add total to result
    result += total;
  }
 
  return result;
}
 
// Test cases
console.log(maxSatisfaction([-1, -8, 0, 5, -9]));  // 14
console.log(maxSatisfaction([4, 3, 2]));  // 20
console.log(maxSatisfaction([-1, -4, -5]));  // 0
 
console.log(maxSatisfactionDP([-1, -8, 0, 5, -9]));  // 14
console.log(maxSatisfactionDP([4, 3, 2]));  // 20
console.log(maxSatisfactionDP([-1, -4, -5]));  // 0
 
console.log(maxSatisfactionOptimized([-1, -8, 0, 5, -9]));  // 14
console.log(maxSatisfactionOptimized([4, 3, 2]));  // 20
console.log(maxSatisfactionOptimized([-1, -4, -5]));  // 0