Leetcode 135: candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

这个题目要求最少给多少糖果，一维数组的最少问题，首先可以想到动态规划， 知道前面给的糖果数，是不是可以推出当前应该给的糖果数目呢？ 一开始通过举例去暴力算，发现从左往右如果是升序，那么糖果数目是可以算的，但是如果出现了降序的情况，那么糖果数目是不可算的，对于这种情况怎么去算呢？ 可以再从右往左扫描，同样如果是升序就可以计算糖果的数目，最后取这两遍计算得出的糖果的最大值，就是最后要给的糖果数。

时间复杂度是O（n）
空间复杂度是O（n）

 class Solution {
public:
    int candy(vector<int>& ratings) {
        //sanity check
        if (ratings.size() == 0) {
            return 0;
        }
        int M[ratings.size()];
        //from left to right, ascending order
        M[0] = 1;
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i-1]) {
                M[i] = M[i-1] + 1;
            } else {
                M[i] = 1;
            }
        }
        int M1[ratings.size()];
        //from right to left, ascending order
        M1[ratings.size()-1] = 1;
        for (int i = ratings.size()-2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1]) {
                M1[i] = M1[i+1]+1;
            } else  {
                M1[i] = 1;
            }
        }
        int sum = 0;
        for (int i = 0; i < ratings.size(); i++) {
            sum += max(M[i], M1[i]);
        }
        return sum;
    }
};