Problems/1402. (H) Reducing Dishes/Java/solution.java
<gh_stars>0class Solution {
  public int maxSatisfaction(int[] satisfaction) {
    // greedy dynamic programming

    Arrays.sort(satisfaction);

    int maxSatisfaction = 0;
    int suffixSum = 0;
    // exit early when suffix sum becomes negative
    for (int i = satisfaction.length - 1; i >= 0 && suffixSum + satisfaction[i] > 0; i--) {
      suffixSum += satisfaction[i];
      maxSatisfaction += suffixSum;
    }
    return maxSatisfaction;
  }
}
