Simple C++ Solution using MaxHeap | No BS
Intuition\n##### To maximize the sum of happiness, it\'s intuitive to select the k highest values from the given array of happiness. \n\n# Approach\nThe approac
# Intuition\n##### To maximize the sum of happiness, it\'s intuitive to select the k highest values from the given array of happiness. \n\n# Approach\nThe approach is to use a max heap (priority queue) to efficiently find the k maximum values from the array. First, we push all the elements of the array into the max heap. Then, we extract the k maximum values from the heap and calculate the sum of happiness by subtracting the index of each value from its corresponding happiness value, ensuring that the resulting happiness is not negative. Finally, we return the total sum of happiness.\n\n# Complexity\n- Time complexity: \n  - Pushing all elements into the priority queue takes O(n log n) time, where n is the size of the `happiness` array.\n  - Extracting the k maximum values takes O(k log n) time.\n  - Overall time complexity: O((n + k) log n), or O(n log n) if k is constant.\n- Space complexity: \n  - The space complexity is O(n) due to the priority queue storing all elements of the `happiness` array.\n\n# Code\n```cpp\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        \n        // we can be greedy here and find the k maximums first.\n        // for that we can use a maxheap\n\n        priority_queue<int> maxHeap;\n\n        // push all the elements of the array into the priority queue\n        for(int num : happiness) maxHeap.push(num);\n\n        // extract the k maximums\n        long long ans = 0, i = 0;\n        while(k--){\n            // the happiness can never be less than 0 so we are taking care of that\n            ans += (maxHeap.top() - i > 0) ? maxHeap.top() - i : 0;\n            maxHeap.pop();\n            i++;\n        }\n\n        return ans;\n    }\n};\n
['Array', 'Greedy', 'Heap (Priority Queue)', 'C++']