C++ | TC: O(nlogn) | SC: O(1)
Intuition\nThe goal is to find the largest sum after performing k negations on elements in the array. To achieve this, we sort the array and then iterate throug
# Intuition\nThe goal is to find the largest sum after performing k negations on elements in the array. To achieve this, we sort the array and then iterate through it. We negate negative numbers until either k becomes zero or we encounter a non-negative number. If k remains after the loop, we consider performing additional negations on the smallest element to maximize the sum.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Sort the input array nums to ensure that negative numbers are at the beginning.\n2. Iterate through the sorted array, negating negative numbers until either k becomes zero or we encounter a non-negative number.\nIf k remains after the loop, consider performing additional negations on the smallest element to maximize the sum by applying sort again.\n4. Finally, calculate the sum of the modified array and return it.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(nlogn)\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       int n = nums.size();\n        sort(nums.begin(), nums.end());\n        int sum = 0;\n        for(int i = 0 ; i < n && k ; i++){\n            cout << nums[i] << " ";\n            if(nums[i] < 0){\n                nums[i] *= -1;\n                k--;\n                }\n            else if(nums[i] == 0 || nums[i] > 0){\n                break;\n            }\n        }\n        sort(nums.begin(), nums.end());\n        if(k){\n            if(k%2 != 0) nums[0] *= -1;\n                    k = 0;           \n        }\n        for(auto it: nums) sum += it;\n        return sum;\n    }\n};\n```
['Greedy', 'Sorting', 'C++']