LeetCode 135. 分发糖果***

进行左右两次遍历；

自己想的是寻找最小值，然后从多个最小值选择一个以该值为起点，左右递增序列最长；

但是发现一是下降难以确定下降多少，二是必定会爆时间；

题解采用左右两次遍历；

两个方向全部满足以下的特点：

1. 当rating[i]>rating[i-1]时，i分的糖果比i-1多加1；
2. 当条件一不成立的时候，直接等于一；

最后每个节点选左右两个方向的最大值；

问题是为什么最大值是成立的？

考虑一下，当irating[j];

从左到右，可以知道j的糖果必定小于i的；

从右到左，可以知道i的糖果必定是大于j的；

所以取到最大值，既可以满足左至右遍历，也可以满足右至左遍历；

class Solution {
public:
    int candy(vector& ratings) {
        int ret=0;
        int n=ratings.size();
        vectordp(n,0);
        vectorkp(n,0);
        for(int i=0;i
            if(i>0&&ratings[i]>ratings[i-1]){
                dp[i]=dp[i-1]+1;
            }else{
                dp[i]=1;
            }
        }
        for(int i=n-1;i>=0;i--){
            if(iratings[i+1]){
                kp[i]=kp[i+1]+1;
            }else{
                kp[i]=1;
            }
        }
        for(int i=0;i
            ret+=max(dp[i],kp[i]);
        }
        return ret;
    }
};