Beats 99.97% Time⌛🔥 99.10% Space💾🔥| Python, C++ 💻 | Clear Explanation📗
Beats 99.97% Time\u231B\uD83D\uDD25 99.10% Space\uD83D\uDCBE\uD83D\uDD25| Python, C++ \uD83D\uDCBB | Clear Explanation\uD83D\uDCD7\n\n## 1. Proof\n\n### 1.1. Py
# Beats 99.97% Time\u231B\uD83D\uDD25 99.10% Space\uD83D\uDCBE\uD83D\uDD25| Python, C++ \uD83D\uDCBB | Clear Explanation\uD83D\uDCD7\n\n## 1. Proof\n\n### 1.1. Python3\n![image.png](https://assets.leetcode.com/users/images/19967664-6733-4e70-95ce-ecae55ecdcc9_1715251788.976113.png)\n\n### 1.2. C++\n![image.png](https://assets.leetcode.com/users/images/4e81912b-7388-4f5a-89d1-e643d5e04110_1715251849.2357152.png)\n\n\n## 2. Algorithms\n- Sorting\n- Greedy\n\n## 3. Code (with explanation each line)\n```python3 []\nclass Solution:\n    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:\n        res = 0 # Result\n        cur_k = k # Current k after each pick\n        happiness.sort() # Top of stack contains max happiness\n        \n        while cur_k > 0: # While budget is enough for picking (each iteration indicates each pick)\n            pick = happiness.pop() # Greedy: always pick top of stack for max happiness\n            picked = k - cur_k # Number of times we\'ve picked, and also the amount of happiness to subtract from the current pick\n            if pick > picked: # Ensure the current pick will still be positive after subtracting from it\n                res += (pick - picked) # Add the positive subtracted happiness to result\n            else: # After subtracting, if happiness is still <= 0 even though we tried to be greedy, that means there\'s nothing more to add to result\n                break\n            cur_k -= 1 # -1 turn of picking\n        \n        return res # Result\n```\n\n```cpp []\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        long long int res = 0;\n        long long int pick = 0, picked = 0;\n        int cur_k = k;\n        sort(happiness.begin(), happiness.end());\n\n        while (cur_k > 0) {\n            pick = happiness.back(); // Greedy: get top of stack\n            happiness.pop_back(); // Pop top of stack\n            picked = k - cur_k;\n            if (pick > picked) {\n                res += (pick - picked);\n            }\n            else {\n                break;\n            }\n            cur_k--;\n        }\n        return res;\n    }\n};\n```\n\n## 4. Complexity\n- Time complexity: $$O(k)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n### Upvote if you find this solution helpful, thank you \uD83E\uDD0D
['Array', 'Greedy', 'Sorting', 'C++', 'Python3']