One-pass O(n) with O(1) space, shortest solution easy to understand
We use inc to record the length of the current (or the last) increasing sequence\n We use dec to record the length of the current decresing sequence\n### Scan t
* We use ```inc``` to record the length of the **current (or the last)** increasing sequence\n* We use ```dec``` to record the length of the current decresing sequence\n### Scan the ```ratings```, there are 3 cases:\n1. Sequence is increasing:\n\t* If the sequence was previously decresing, reset ```inc``` to ```1```\n\t* Bump up ```inc``` and increase our final answer ```ans``` by ```inc``` (*give the last child ```inc``` candies*)\n\t* Since the sequence is currently increasing, reset ```dec``` to ```1```\n2. Sequence is decreasing:\n\t* Bump up ```dec``` and increase ```ans``` by ```dec - 1```. *Meaining we give ```1``` candy to the last child, and bump up the candies for everyone before him, expect the first child in the decreasing sequence.*\n\t* Bump up ```ans``` if ```dec > inc```: *because the length of the current decreasing sequence exceeds the last increasing sequence, which implies we need to bump up the candies for the first child in the decreasing sequence. Consider the sample ```[1, 5, 3, 2, 1]```: initially we gave the second child only 2 candies, but when we reach ```ratings[3]=2```, 2 is not enough for him*\n3. Otherwise (```ratings[i] == ratings[i - 1]```): simply increment ```ans``` (*1 candy for the child is enough*) and reset ```inc``` and ```dec``` to 1.\n\n```\n    public int candy(int[] ratings) {\n        int ans = 1, inc = 1, dec = 1;\n        for (int i = 1; i < ratings.length; i++) {\n            if (ratings[i] > ratings[i - 1]) {\n                if (i > 1 && ratings[i - 1] < ratings[i - 2]) inc = 1;\n                ans += ++inc;\n                dec = 1;\n            }\n            else if (ratings[i] < ratings[i - 1]) {\n                dec++;\n                ans += dec - 1;\n                if (dec > inc) ans++;\n            }\n            else {\n                ans++;\n                inc = 1;\n                dec = 1;\n            }\n        }\n        return ans;\n    }\n```
[]