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.
  

   1 public class Solution {
   2     public int candy(int[] ratings) {
   3         int N = ratings.length;
   4         int c [] = new int [N];
   5         int sum = N;
   6         for(int i=0,k=1;i<N;i++){
   7             if(i>0 && ratings[i]>ratings[i-1]){
   8                 c[i] = k++;
   9             }
  10             else{
  11                 k=1;
  12             }
  13         }
  14         for(int i=N-1,k=1;i>=0;i--){
  15             if(i<N-1 && ratings[i]>ratings[i+1]){
  16                 c[i] = Math.max(k++,c[i]);
  17             }
  18             else{
  19                 k=1;
  20             }
  21         }
  22         for(int i=0;i<N;i++){
  23             sum+= c[i];
  24         }
  25         return sum;
  26     }
  27 }

  View Code

   

Candy

原文：http://www.cnblogs.com/krunning/p/3560674.html