# LC 1005. Maximize Sum Of Array After K Negations

### [Problem link](https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/)

###### tags: `leedcode` `python` `c++` `easy` `Greedy` `Heap`

Given an integer array <code>nums</code> and an integer <code>k</code>, modify the array in the following way:

- choose an index <code>i</code> and replace <code>nums[i]</code> with <code>-nums[i]</code>.

You should apply this process exactly <code>k</code> times. You may choose the same index <code>i</code> multiple times.

Return the largest possible sum of the array after modifying it in this way.

**Example 1:**

Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose index 1 and nums becomes [4,-2,3].

**Example 2:**

Input: nums = [3,-1,0,2], k = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].

**Example 3:**

Input: nums = [2,-3,-1,5,-4], k = 2
Output: 13
Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].

**Constraints:**

- <code>1 <= nums.length <= 10⁴</code>
- <code>-100 <= nums[i] <= 100</code>
- <code>1 <= k <= 10⁴</code>

## Solution 1 - Greedy
#### Python

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key = lambda x: abs(x), reverse = True)
        res = 0

        for i in range(len(nums)):
            if k > 0 and nums[i] < 0:
                nums[i] = -nums[i]
                k -= 1
        
        if k > 0:
            if k % 2:
                nums[-1] = -nums[-1]
        
        return sum(nums)

#### C++

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), [](int &num1, int &num2) {return abs(num1) > abs(num2);});

        int res = 0;
        for (int& num: nums) {
            if (num < 0 && k > 0) {
                num = -num;
                k--;
            }
            res += num;
        }
        if (k % 2) {
            res -= nums.back() * 2;
        }
        return res;
    }
};

## Solution 2 - Heap

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        heapify(nums)
        
        for _ in range(k):
            heappush(nums, -heappop(nums))
        
        return sum(nums)

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ------------------- | --------------- | ---------------- |
>| Solution 1 (python) | O(nlogn) | O(n) |
>| Solution 1 (c++) | O(nlogn) | O(1) |
>| Solution 2 | O(nlogn) | O(n) |

## Note
sol1. c++的想法比較好, 參考c++的就好