题目描述

原题链接：1005. K 次取反后最大化的数组和

解题思路

模拟变化
将数列排序，按数列从小到大位置取相反数。

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {                
        sort(nums.begin(), nums.end());
        // 最小的数，大于0，则只变化第一个最小的数
        if(nums[0] > 0) {
            for(int i = 0, j = 0; i < nums.size() && j < k; j++)        nums[i] = -nums[i];
        }
        // 最小的数，小于0。最小的数等于0时，相反数不变
        else if(nums[0] < 0) {
            for(int i = 0, j = 0; j < k; j++) {
                if(nums[i] < 0) {           // 负数变正数
                    nums[i] = -nums[i];
                    if(i + 1 < nums.size())     i++;    // 保证加后不越界
                } else if(nums[i] == 0) {   // 遇到0时，不变
                    continue;
                } else if(nums[i] > 0) {    // 遇到第一个大于0的，左右值对比，变更小的那个
                    if(nums[i - 1] < nums[i])       nums[i - 1] = -nums[i - 1];
                    else                            nums[i] = -nums[i];
                }
            }
        }
        int res = 0;
        for(int num : nums) {
            res += num;
        }   

        return res;
    }
};

变负数，根据k值变非负数
局部最优解：（1）负数按从小到大顺序变为正数；（2）负数变为后，还有剩余k的话，将最小非负数进行变化。
全局最优解：整个数组和最大

class Solution {
public:
    static bool cmp(int a, int b)  {        
        return abs(a) > abs(b);             // 按绝对值升序排序
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), cmp);
        for(int i = 0; i < nums.size(); i++) {      // 将负数全变为正数
            if(nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        // 若还剩余奇数个k，则让最小的那个正数变为负数。偶数个k，最后还为正数
        if(k % 2 == 1)      nums[nums.size() - 1] *= -1;
        int res = 0;
        for(int num : nums)     res += num;
        return res;
    }
};

参考文章：1005. K 次取反后最大化的数组和