candy. minimum num of candy

candy.cpp

/*
 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? 
*/
class Solution {
public:
    int candy(vector<int> &ratings) {
        //scan from left and right, assign more candy if rating is larger than left/right nabor
        //Note: in right scan, only update the numCandy if it's less than needed.
        
        int n = ratings.size();
        if (n <= 0)
            return 0;
        vector<int> numCandy(n, 1);
        //scan from left, give more candy for higher rating
        for(int i=1; i<n; i++) {
            if (ratings[i] > ratings[i-1] )
                numCandy[i] = numCandy[i-1]+1;
        }
        
        int totalNum = numCandy[n-1];
        //scan from right
        for(int i=n-2; i>=0 ; i--) {
            if (ratings[i] > ratings[i+1] && numCandy[i] < numCandy[i+1] + 1 )
                numCandy[i] = numCandy[i+1]+1;
            totalNum += numCandy[i];
        }
        
        return totalNum;
    }
};