Beats 100% || 79ms || Explained Approach || C++ || Java || Python
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to select k children with the maximum happiness value. Therefore, sorting the h
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to select k children with the maximum happiness value. Therefore, sorting the happiness vector in non-increasing order seems like a reasonable approach.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sort the happiness vector in non-increasing order.\n```\nsort(happiness.begin(), happiness.end(), greater<int>());\n```\n2. Initialize sum(long long) which will store the maximum happiness value.\n```\nlong long sum = 0;\n```\n3. Iterate k times over the sorted happiness vector. Remember to decrement the happiness of every other happiness value.\n```\nhappiness[i] = max(0, happiness[i]-i);\nsum += happiness[i];\n```\n# Complexity\n- Time complexity: O(nlog(n))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);\n        sort(happiness.begin(), happiness.end(), greater<int>());\n        long long sum = 0;\n        for(int i = 0; i < k; i++) {\n            happiness[i] = max(0, happiness[i]-i);\n            sum += happiness[i];\n        }\n        return sum;\n    }\n};\n```\n```Java []\nclass Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n        Arrays.sort(happiness);\n        long sum = 0;\n        for (int i = happiness.length - 1; i >= happiness.length - k; i--) {\n            happiness[i] = Math.max(0, happiness[i] - (happiness.length - 1 - i));\n            sum += happiness[i];\n        }\n        return sum;\n    }\n}\n```\n```Python []\nfrom typing import List\n\nclass Solution:\n    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:\n        happiness.sort(reverse=True)  \n        total_sum = 0\n        for i in range(k):\n            happiness[i] = max(0, happiness[i] - i)  \n            total_sum += happiness[i]  \n        return total_sum  \n\n```
['Array', 'Greedy', 'Sorting', 'C++', 'Java', 'Python3']