// Candy

// 备忘录法，时间复杂度O(n)，空间复杂度O(n)

// @author fancymouse (http://weibo.com/u/1928162822)

class Solution {

public:

int candy(const vector<int>& ratings) {

vector<int> f(ratings.size());

int sum = 0;

for (int i = 0; i < ratings.size(); ++i)

sum += solve(ratings, f, i);

return sum;

}

int solve(const vector<int>& ratings, vector<int>& f, int i) {

if (f[i] == 0) {

f[i] = 1;

if (i > 0 && ratings[i] > ratings[i - 1])

f[i] = max(f[i], solve(ratings, f, i - 1) + 1);

if (i < ratings.size() - 1 && ratings[i] > ratings[i + 1])

f[i] = max(f[i], solve(ratings, f, i + 1) + 1);

}

return f[i];

}

};