Greedy || C++ || Java || Python || Commented Code
Intuition && approach\n \nThe first step is to create a vector of integers called candies with the same size as the ratings array. Each element of candies will 
# Intuition && approach\n<!--  -->\nThe first step is to create a vector of integers called candies with the same size as the ratings array. Each element of candies will store the number of candies that the corresponding child should get. We initialize all elements of candies to 1.\n\nIn the next step, we iterate through the ratings array from left to right. For each child, we check if its rating is higher than the rating of its left neighbor. If so, we update the value of candies[i] to candies[i-1] + 1. This is because a child with a higher rating should get more candies than its neighbor.\n\nWe also iterate through the ratings array from right to left. For each child, we check if its rating is higher than the rating of its right neighbor. If so, we update the value of candies[i] to the maximum of candies[i] and candies[i+1] + 1. This is because a child with a higher rating should never get fewer candies than its neighbor.\n\nFinally, we iterate through the candies array and add up all the elements. This gives us the total number of candies that we need to distribute.\n\n\n\n# Complexity\n- Time complexity: O(n)\nThe time complexity of this solution is O(n), where n is the number of children. This is because we iterate through the ratings array twice.\n- Space complexity:O(n)\nThe space complexity of this solution is O(n), where n is the number of children. This is because we create a vector of size n to store the number of candies for each child.\n\n# Code\n```\nclass Solution {\npublic:\n    int candy(vector<int>& ratings) {\n        int n = ratings.size();\n        vector<int> candies(n, 1);\n\n        // Iterate from left to right and update candies[i] if ratings[i] > ratings[i - 1].\n        for (int i = 1; i < n; i++) {\n            if (ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {\n                candies[i] = candies[i - 1] + 1;\n            }\n        }\n\n        // Iterate from right to left and update candies[i] to the maximum of candies[i] and candies[i + 1] + 1.\n        for (int i = n - 2; i >= 0; i--) {\n            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {\n                candies[i] = candies[i + 1] + 1;\n            }\n        }\n\n        // Calculate the total number of candies.\n        int total = 0;\n        for (int i = 0; i < n; i++) {\n            total += candies[i];\n        }\n\n        return total;\n    }\n};\n\n```\n```\n//java code \nclass Solution {\n    public int candy(int[] ratings) {\n        int n = ratings.length;\n        int[] dp = new int[n];\n        Arrays.fill(dp, 1);\n\n        // Iterate from left to right and update dp[i] if ratings[i] > ratings[i - 1].\n        for (int i = 1; i < n; i++) {\n            if (ratings[i] > ratings[i - 1]) {\n                dp[i] = dp[i - 1] + 1;\n            }\n        }\n\n        // Iterate from right to left and update dp[i] to the maximum of dp[i] and dp[i + 1] + 1.\n        for (int i = n - 2; i >= 0; i--) {\n            if (ratings[i] > ratings[i + 1]) {\n                dp[i] = Math.max(dp[i], dp[i + 1] + 1);\n            }\n        }\n\n        // Calculate the total number of candies.\n        int total = 0;\n        for (int i = 0; i < n; i++) {\n            total += dp[i];\n        }\n\n        return total;\n    }\n}\n```\n```\n//python code\nclass Solution:\n    def candy(self, ratings: List[int]) -> int:\n        n = len(ratings)\n        dp = [1] * n\n\n        # Iterate from left to right and update dp[i] if ratings[i] > ratings[i - 1].\n        for i in range(1, n):\n            if ratings[i] > ratings[i - 1]:\n                dp[i] = dp[i - 1] + 1\n\n        # Iterate from right to left and update dp[i] to the maximum of dp[i] and dp[i + 1] + 1.\n        for i in range(n - 2, -1, -1):\n            if ratings[i] > ratings[i + 1]:\n                dp[i] = max(dp[i], dp[i + 1] + 1)\n\n        # Calculate the total number of candies.\n        total = sum(dp)\n\n        return total\n```\n\n\n
['Dynamic Programming', 'Greedy', 'Python', 'C++', 'Java', 'Python3']