Maximize Sum Of Array After K Negations

Problem

Given an integer array nums and an integer k, modify the array in the following way:

• choose an index i and replace nums[i] with -nums[i].

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

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

Constraints

• 1 <= nums.length <= 104
• -100 <= nums[i] <= 100
• 1 <= k <= 104

Solution

The problem Maximize Sum Of Array After K Negations can be solved by converting as much negative integers as possible. If even number of k is left afterwards, then the same integer can be flipped k times to yield the same number. If even number of k is left, then the smallest integer can be flipped to negative to yield the largest possible sum.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++, k--)
        {
            if (nums[i] > 0 || k == 0)
                break;

            nums[i] *= -1;
        }

        int neg = (k % 2) ? *min_element(nums.begin(), nums.end()) : 0;
        return accumulate(nums.begin(), nums.end(), -2 * neg);
    }
};