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.

package com.bupt.acm.leetcode;import java.util.Arrays;public class Candy {    /**     * 本算用于求解当等级比其高时值加倍     * @param ratings     * @return     */    public int sum=0;    public int candy(int[] ratings){                if(ratings==null||ratings.length==0){            return 0;        }        int min=ratings[0];        int length=ratings.length;        if(ratings.length==1){            return 1;        }                int[] score=new int[length];        for(int i=0;i
     
      ratings[i]){                min=ratings[i];            }        }        for(int i=0;i
      
       =ratings[now]){                return 1;            }else{                return computeCandy(ratings, beg-1, beg, now,score)+1;            }        }else if(now==0){
   //表示第一个元素            if(ratings[now]<=ratings[end])                return 1;            else{                return computeCandy(ratings, now, end, end+1,score)+1;            }        }else{
   //表示其他元素            int a=ratings[beg],b=ratings[now],c=ratings[end];            if(a==b&&b==c){
   //a=b=c                return 1;            }else if(b>a&&b>c){
   //a
       c                return Math.max(computeCandy(ratings, beg-1, beg, now,score)+1, computeCandy(ratings, now, end, end+1,score)+1);            }else if(b>a&&b<=c){
   // a<=c                return computeCandy(ratings, beg-1, beg, now,score)+1;            }else if(b<=a&&b>c){
   //a
      
     

 上述算法最后一个样例超时，

新算法：

初始化所有小孩糖数目为1，从前往后扫描，如果第i个小孩等级比第i-1个高，那么i的糖数目等于i-1的糖数目+1；从后往前扫描，如果第i个的小孩的等级比i+1个小孩高,但是糖的数目却小或者相等，那么i的糖数目等于i+1的糖数目+1

public int candy2(int[] ratings){        if(ratings==null||ratings.length==0)            return 0;        if(ratings.length==1)            return 1;        int sum=0;        int length=ratings.length;        int[] scores=new int[length];        for(int i=0;i
     
      ratings[i-1]){                scores[i]=scores[i-1]+1;            }        }        for(int i=length-1;i>0;i--){            if(ratings[i-1]>ratings[i]){                if(scores[i-1]<=scores[i]){                    scores[i-1]=scores[i]+1;                }            }        }        for(int i=0;i