Leetcodeダイナミック企画キャンディー

この記事はsenlieオリジナルです。転載はこの住所を残してください。http://blog.csdn.net/zhengsenlie
キャンディ 
Total Acceepted: 16494 
Total Submissions: 87468 My Submissions
The re are N チルドレンstanding in a line.Each child is assigned a rating value.
You are giving candies to these children subjeced 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？
n人の子供は子供一人に採点があります。子供に飴を配る。要求：1）子供一人につき少なくとも1粒の砂糖2）採点の高い子供が出す飴は彼の隣の子供より多くの考え方があります。左右dpは1列のcandy[n]を使い、i番目の子供が出すべき最少のキャンデーの数配列ratings[n]は子供一人についての点数を表します。candy[i]=candy[i-1]+1,if rating s[i]>ratings[i-1]2.右から左にスキャンして、candy[i]=candy[i]，if ratings[i]<=ratings[i+1];candy[i]=max(candy[i]，candy[i＋1]+1)、if ratings[i]>ratings[i＋1]3.accumulte(candy，candy+n，0)複雑度：時間O(n)、空間O(n)

int candy(vector<int> &ratings){
	int n = ratings.size();
	vector<int> candy(n, 1);
	for(int i = 1; i < n; ++i){
		candy[i] = ratings[i] <= ratings[i - 1] ? 1 : candy[i - 1] + 1;
	}
	for(int i = n - 2; i > -1;--i){
		candy[i] = ratings[i] <= ratings[i + 1] ? candy[i] : max(candy[i], candy[i + 1] + 1);
	}
	return accumulate(candy.begin(), candy.end(), 0);
}