A cpp solution using top-down dp


  • 0
    O
    class Solution {
        int go(int n, vector<int> &ratings, vector<int> &dp) {
            if (dp[n] != -1) return dp[n];
            int lf = 0, rg = 0;
            if (n > 0 && ratings[n] > ratings[n - 1]) lf = go(n - 1, ratings, dp);
            if (n < ratings.size() - 1 && ratings[n] > ratings[n + 1]) rg = go(n + 1, ratings, dp);
            return dp[n] = max(lf, rg) + 1;
        }
    public:
        int candy(vector<int>& ratings) {
            int N = ratings.size();
            vector<int> dp(ratings.size(), -1);
            for (int i = 0; i < N; i++) {
                bool ok = 1;
                if (i - 1 >= 0 && ratings[i - 1] < ratings[i]) ok = 0;
                if (i + 1 <= N - 1 && ratings[i + 1] < ratings[i]) ok = 0;
                if (ok) dp[i] = 1;
            }
            for (int i = 0; i < N; i++) if (dp[i] == -1) go(i, ratings, dp);
            int ans = 0;
            for (auto i : dp) ans += i;
            return ans;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.