👏Beats 97.44% of users with Java🎉|| ⏩Fastest 2 Approaches💯||✅Easy & Well Explained Solution🔥💥
Intuition\nGiven an array of happiness levels, decrement elements up to a limit, find the maximum sum of positive happiness values among top \'k\' elements.\n\n
# Intuition\nGiven an array of happiness levels, decrement elements up to a limit, find the maximum sum of positive happiness values among top \'k\' elements.\n\n# I Think This Can Help You(For Proof Click on the Image)\n[![Screenshot 2024-02-24 232407.png](https://assets.leetcode.com/users/images/d1402191-a350-4637-9ccb-2f5c7ade043e_1715224250.913294.png)](https://leetcode.com/problems/maximize-happiness-of-selected-children/submissions/1253152217/?envType=daily-question&envId=2024-05-09)\n\n\n# Approach\n## Approach 1:\n1. **Sort the Array**: Initially, the array of happiness is sorted in ascending order. This is done to ensure that we start with the highest happiness values.\n\n```java\nArrays.sort(happiness);\n```\n\n2. **Initialize Variables**: \n   - `dec`: This variable is used to keep track of the number of decrements made.\n   - `max`: This variable stores the maximum sum of happiness.\n   - `value`: This variable represents the current value of happiness after decrementing.\n\n```java\nint dec = 0;\nlong max = 0;\nint value = 0;\n```\n\n3. **Iterate through the Sorted Array Backwards**: We iterate through the sorted array from the end towards the beginning, considering the top `k` elements.\n\n```java\nfor (int i = happiness.length - 1; i >= happiness.length - k; i--) {\n    // Code block inside loop\n}\n```\n\n4. **Decrement and Calculate Happiness**:\n   - `value = happiness[i] - dec;`: Calculate the current happiness value after decrementing it based on the `dec` value.\n   - `dec++`: Increment the decrement counter for the next iteration.\n   - Check if the decremented value is greater than 0, if yes, add it to the `max` variable.\n\n```java\nvalue = happiness[i] - dec;\ndec++;\nif (value > 0) {\n    max += value;\n}\n```\n\n5. **Return the Maximum Sum of Happiness**: Finally, return the calculated maximum sum of happiness.\n\n```java\nreturn max;\n```\n## Approach 2:\n1. **Sort the Array**:\n   - Sort the array of happiness in ascending order.\n\n```java\nArrays.sort(happiness);\n```\n\n2. **Initialize Variables**:\n   - `dec`: Counter to keep track of the number of decrements.\n   - `n`: Length of the happiness array.\n   - `ans`: Variable to store the maximum sum of happiness.\n\n```java\nint dec = 0, n = happiness.length;\nlong ans = 0;\n```\n\n3. **Iterate through the Sorted Array Backwards**:\n   - Iterate through the sorted array starting from the end and consider the top `k` elements.\n\n```java\nfor (int i = n - 1; i >= n - k; i--) {\n    // Code block inside loop\n}\n```\n\n4. **Decrement and Calculate Happiness**:\n   - Calculate the current happiness value after decrementing it based on the `dec` value.\n   - Add the decremented happiness to `ans` only if it\'s greater than 0.\n\n```java\nans += Math.max(0, happiness[i] - dec);\ndec++;\n```\n\n5. **Return the Maximum Sum of Happiness**:\n   - Return the calculated maximum sum of happiness stored in `ans`.\n\n```java\nreturn ans;\n```\n\n# Complexity\n- Time complexity:\nApproach 1: O(n log n)\nApproach 2: O(n log n)\n\n- Space complexity:\nApproach 1: O(1)\nApproach 2: O(1)\n\n# Code\n## Approach 1:\n```\nclass Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n        Arrays.sort(happiness);\n        int dec = 0;\n        long max=0;\n        int value=0;\n        for(int i=happiness.length-1;i>=happiness.length-k;i--){\n            value = happiness[i]-dec;\n            dec++;\n            if(value>0)\n            {\n                max += value;\n            }\n        }\n        return max;\n    }\n}\n```\n## Approach 2:\n```\nclass Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n        Arrays.sort(happiness);\n        int dec = 0,n=happiness.length;\n        long ans=0;\n        for(int i=n-1;i>=n-k;i--){\n            ans += Math.max(0,happiness[i]-dec);\n            dec++;\n        }\n        return ans;\n    }\n}\n```\n\n![_88a70899-aa2e-436d-8727-f561b4e9f641.jpeg](https://assets.leetcode.com/users/images/d71851eb-1424-4c7d-8f18-7ab8d6134fda_1715224513.6000948.jpeg)\n
['Array', 'Greedy', 'Sorting', 'Java']