class Solution {
public:
int maxSatisfaction(vector& sat) {
// we'll greedily only consider a suffix of the sorted array
sort(sat.begin(), sat.end());
int cmax = 0;
int sum = 0;
int csum = 0;
int i = sat.size(); // iterate from n - 1 to 0
while(i--) {
// calulate current satisfaction
csum += sat[i];
sum += csum;
// compare with cmax
cmax = max(cmax, sum);
}
return cmax;
}
};