135. Candy

135. Candy

贪心

分析问题：概率大的比相邻的得到的糖果多，肯定是+1操作，先从左到右遍历，比较每一个点与其左边点的大小关系，得到一个值，然后载从右往左依次比较。两次遍历后相当于左右邻居都做了比较，去较大的那个即可。

体会：重点在于根据题目的规则对问题进行分析，这道题的规则是与其左右邻居相比，分析，先比较左边，在比较右边，然后贪心的取其中较大值。

class Solution {
    public int candy(int[] ratings) {
        int len=ratings.length;
        int sum=len;
        int dpleft[]=new int[len];
        int dpright[]=new int[len];
        for(int i=1;i<len;i++)
            if(ratings[i]>ratings[i-1])
                dpleft[i]=dpleft[i-1]+1;
         for(int i=len-1;i>0;i--)
            if(ratings[i-1]>ratings[i])
                dpright[i-1]=dpright[i]+1;
        for(int i=0;i<len;i++)
            sum+=Math.max(dpleft[i],dpright[i]);
        return sum;
    }
}