学步园

int candySolution(vector<int> &ratings)
{
		if(ratings.empty()) return 0;
		int n = ratings.size();

		vector<int> candyNum(n);
		//这里不能用for(auto x:candyNum) x=1;这样无法修改candyNum的值的。
		for(int i=0; i<n; i++)
		{
			candyNum[i] = 1;
		}

		for(int i=1; i<n; i++)
		{
			if(ratings[i-1]<ratings[i])
				candyNum[i] = candyNum[i-1]+1;
		}
		//应付权值诸如 1 3 4 2 1 3这样的例子
		//正确的分配结果应该是1 2 3 2 1 2
		for(int i=n-2; i>=0; i--)
		{
			if(ratings[i+1]<ratings[i] && candyNum[i]<(candyNum[i+1]+1))
				candyNum[i] = candyNum[i+1]+1;
		}

		int sum = 0;
		for(int i=0; i<n; i++)
			sum += candyNum[i];

		return sum;
}