Easiest approach with sorting
Intuition\n Describe your first thoughts on how to solve this problem. \nGreedily select the first k largest element and/or stop until you see the first 0.\n\n#
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nGreedily select the first $$k$$ largest element and/or stop until you see the first $$0$$.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. sort `happiness` in descending order\n2. initialize `max=0` to keep track of max later and to return\n3. have a loop looping through the element from high to low\n4. minus `i` for each `happiness[i]` as it will be encounterd after ith step. \n5. If `happiness[i] - i <= 0` or `k == 0` break, as we will not making more progress to increase the max\n6. For each step, we increase max by `happiness[i] - i` and decrement `k`\n7. return `max`\n\n# Complexity\n- Time complexity: $$O(n log n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$ sorting for python takes $$O(n)$$ additional space\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:\n        happiness.sort(reverse=True)\n        max = 0\n        for i in range(len(happiness)):\n            if (happiness[i] - i <= 0 or k == 0):\n                break\n            max += happiness[i] - i\n            k -= 1\n\n\n        return max\n\n```
['Array', 'Greedy', 'Sorting', 'Python3']