Reducing Dishes Solutions in C++

/// Source : https://leetcode.com/problems/reducing-dishes/
/// Author : liuyubobobo
/// Time   : 2020-04-11

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(nlogn + n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {

        sort(satisfaction.begin(), satisfaction.end());

        int n = satisfaction.size();
        vector<vector<int>> dp(n, vector<int>(n + 1, INT_MIN));
        return max(0, dfs(satisfaction, 0, 1, dp));
    }

private:
    int dfs(const vector<int>& v, int index, int t, vector<vector<int>>& dp){

        if(index == v.size()) return 0;
        if(dp[index][t] != INT_MIN) return dp[index][t];
        return dp[index][t] = max(t * v[index] + dfs(v, index + 1, t + 1, dp),
                                  dfs(v, index + 1, t, dp));
    }
};


int main() {

    vector<int> nums1 = {-1,-8,0,5,-9};
    cout << Solution().maxSatisfaction(nums1) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/reducing-dishes/
/// Author : liuyubobobo
/// Time   : 2020-04-11

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(nlogn + n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {

        sort(satisfaction.begin(), satisfaction.end());

        int n = satisfaction.size();
        vector<vector<int>> dp(n, vector<int>(n + 1, INT_MIN));
        for(int i = 0; i < n; i ++) dp[i][n] = satisfaction[i] * n;

        for(int t = n - 1; t > 0; t --){
            dp[n - 1][t] = satisfaction[n - 1] * t;
            for(int i = n - 2; i >= 0; i --)
                dp[i][t] = max(satisfaction[i] * t + dp[i + 1][t + 1], dp[i + 1][t]);
        }
        return max(0, dp[0][1]);
    }
};


int main() {

    vector<int> nums1 = {-1,-8,0,5,-9};
    cout << Solution().maxSatisfaction(nums1) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/reducing-dishes/
/// Author : liuyubobobo
/// Time   : 2020-04-11

#include <iostream>
#include <vector>

using namespace std;


/// Greedy
/// Time Complexity: O(nlogn + n)
/// Space Complexity: O(1)
class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {

        sort(satisfaction.begin(), satisfaction.end(), greater<int>());

        int n = satisfaction.size();
        int res = 0, sum = 0;
        for(int e: satisfaction){
            if(sum + e > 0) sum += e, res += sum;
            else break;
        }
        return res;
    }
};


int main() {

    vector<int> nums1 = {-1,-8,0,5,-9};
    cout << Solution().maxSatisfaction(nums1) << endl;

    return 0;
}