Super Simple C++ O(nlog(n)) Solution w/ Explanation
Intuition\nSorting is your best friend here. That way we can make as many negative values as possible become positive (maximizing the final sum).\n\nThe other k
# Intuition\nSorting is your best friend here. That way we can make as many negative values as possible become positive (maximizing the final sum).\n\nThe other key detail to notice is that if every element is already positive, changing the sign of any element twice reduces `k` by $$2$$ without reducing the final sum.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Sort the input\n2. Loop through as many negatives elements as possible, `k` permitting\n3. Lastly check if `k` is odd. If it is, then sort the array again and negate the first (a.k.a. smallest) element\n<!-- Describe your approach to solving the problem. -->\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(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int largestSumAfterKNegations(vector<int>& nums, int k) {\n        sort(nums.begin(),nums.end());\n        int i = 0;\n        while(i<nums.size() && nums[i]<0 && k>0)\n        {\n            nums[i] *= -1;\n            i++;\n            k--;\n        }\n        if(k%2 == 1)\n        {\n            sort(nums.begin(),nums.end());\n            nums[0] *= -1;\n        }\n        int sum = 0;\n        for(int n : nums)\n        {\n            sum += n;\n        }\n        return sum;\n    }\n};\n```
['Greedy', 'Sorting', 'C++']