Candy

Traverse twice: Forward then Backward

Rating: 1 2 3 4 2 1 1

Init: 1 1 1 1 1 1 1

Forward: 1 2 3 4 1 1 1 (istart from 1, compare with left i-1 ), traverse once is not correct

Backward: 1 2 3 3 2 1 1 (rule candy[i+1] + 1, is not correct)

Backward: 1 2 3 4 2 1 1 ( correct: max(candy[i], candy[i+1] + 1) )

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        int sum = 0;
        if (n == 0)
            return 0;

        vector<int> candy(ratings.size(), 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i-1]) {
                candy[i] = candy[i-1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i+1]) {
                candy[i] = max(candy[i], candy[i+1] + 1);
            }
        }

        for (auto i : candy) {
            sum += i;
        }

        return sum;
    }
};