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:
What is the minimum candies you must give?
public class Solution { public int candy(int[] ratings) { if(ratings.length == 0){ return 0; } if(ratings.length == 1){ return 1; } int sum = 0; int candy[] = new int[ratings.length]; Arrays.fill(candy, 1); for(int i = 1; i < ratings.length; i++){ if(ratings[i] > ratings[i - 1]) candy[i] = candy[i-1]+1; } for(int i = ratings.length - 1; i > 0; i--){ if(ratings[i-1] > ratings[i]) candy[i-1] = Math.max(candy[i] + 1,candy[i-1]); } for(int i = 0; i < candy.length ; i ++){ sum += candy[i]; } return sum; } }
原文：http://www.cnblogs.com/joannacode/p/5958892.html