class Solution {
public:
    //这题是滑雪的一维简化版，但是这题很容易看错题意而误解，原本天真的以为只需要计算重复的个数k
    //然后最后的答案为2n - 1 - k，但是这题有一个坑就是如果中间的数比两边的高，如[0,1,0],那么给的糖果应该
    //是[1,2,1]而不是[1,3,1],如果单纯遍历然后判断相邻两数的话容易踩这个坑，说白了就是陷入贪心局部最优。
    //所以本题要用记忆化搜索获取全局最优，参考滑雪那题
    vector<int> f;
    vector<int> w;
    int n;
    int dfs(int x){//记忆化搜索
        if(f[x] != -1) return f[x];//如果被算过，直接返回即可
        f[x] = 1;//保证至少为1，至少获得一个糖果
        if(x > 0 && w[x] > w[x - 1]) f[x] = max(f[x], dfs(x - 1) + 1);//向左滑雪
        if(x + 1 < n && w[x] > w[x + 1]) f[x] = max(f[x], dfs(x + 1) + 1);//向右滑雪
        return f[x];
    }
    int candy(vector<int>& ratings) {
        n = ratings.size();
        w = ratings;
        f.resize(n, -1);//记忆化搜索， 初始化f为-1
        int ans = 0;
        for(int i = 0; i < n; i ++){
            ans += dfs(i);
        }
        return ans;
    }
};