C++ Greedy vs Prefix Sum
Intuition\n Describe your first thoughts on how to solve this problem. \nIt\'s a greedy problem.\nLook at this example. You\'ll find how unfair this rule is.\n\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt\'s a greedy problem.\nLook at this example. You\'ll find how unfair this rule is.\n```\n[60, 80, 100, 100, 100, 100, 100]\n```\ncandies for children\n```\n1, 2, 3, 1, 1, 1, 1\n```\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse prefix sum.It\'s easier to understand. Transverse forward & backward. 3 conditions to consider\n1. ratings[i-1] < ratings[i]: c[i]=c[i-1]+1;\n2. ratings[i-1] ==ratings[i]==ratings[i+1]: c[i]; 1 candy is enough\n3. ratings[i]>ratings[i+1]: c[i]=max(c[i], c[i+1]+1); Use it when backward \n\nThis can be done just using one loop. But the handeling is a little bit subtle.\n\nSupposed one has arrived the peak, i.e. ```c[i]=peak+1```. From index i on, ```ratings[i]``` form a strictly decreasing sebsequence of length down+1. If peak>=down the candies for subdsequence of length ```down+1```.\n```\ncs=[peak+1,down, down-1, ...., 2, 1] \n```\notherwise, i.e. peak<down, when adding 1 more ```ratings[i]``` with ```ratings[i-1]>ratings[i]```\nevery element in ```cs```should be increased by 1 whose total amount is ```down+1```.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n1st code: $O(1)$\n2nd code: $O(n)$\n#  Code using 1 transversal &  O(1) SC\n```\nclass Solution {\npublic:\n    int candy(vector<int>& ratings) {\n        int n=ratings.size();\n        int ans = 1;\n        int up = 0, down = 0, peak = 0;\n         for (int i = 1; i <n; i++) {\n             //ascending\n            if (ratings[i-1] < ratings[i]) {\n                peak = ++up;\n                down = 0;\n                ans+= 1+peak;//c[i]=1+peak\n            } \n            //slope=0\n            else if (ratings[i-1] == ratings[i])  {\n                peak =up = down = 0;\n                ans++;//c[i]=1\n            } \n            else {//decreasing\n                up = 0;\n                down++;//length for decreasing subsequence\n                ans += (peak<down)? down+1: down;\n                //If peak>=down the candies for subdsequence of length down+1\n                //cs=[peak+1,down, down-1, ...., 2, 1] otherwise when adding 1 more \n                //every element in cs should be increased by 1 which amount down+1\n            }\n        }\n        return ans;\n    }\n};\n```\n# Prefix Sum\n```\nclass Solution {\npublic:\n    void print(vector<int>& c){\n        for(int i=0; i<c.size(); i++)\n            cout<<c[i]<<",";\n        cout<<endl;\n    }\n    int candy(vector<int>& ratings) {\n        int n=ratings.size();\n        vector<int> c(n, 1);\n\n        for (int i=1; i<n; i++){\n            if (ratings[i]>ratings[i-1]) \n                c[i]=c[i-1]+1;\n        }\n        for (int i=n-2; i>=0; i--)\n            if (ratings[i]>ratings[i+1]) \n                c[i]=max(c[i], c[i+1]+1);\n    //    print(c);\n        return accumulate(c.begin(), c.begin()+n,0);\n    }\n};\n```
['Greedy', 'Prefix Sum', 'C++']