1005. K 次取反后最大化的数组和

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

> 我的解法

class Solution {
public:
    //取反的顺序为 负数、0、正数（优先级是小的优先）
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        std::sort(nums.begin(),nums.end());
        int len = nums.size();
        int target = 0;
        if(*nums.begin() > 0){
            k = k%2;
            if(k == 1){
                nums[0] = -nums[0];
            }
        }
        else if(*nums.begin() < 0){
            auto iter = std::find(nums.begin(),nums.end(),0);
            if(iter == nums.end()){
                for(int i = 0;i < len && k > 0 && nums[i] < 0;i++){
                    nums[i] = - nums[i];
                    k--;
                }
                if(k > 0){
                    return largestSumAfterKNegations(nums,k);
                }
            }
            else{
                for(auto it = nums.begin();it != iter && k > 0; it++){
                    *it = -*it;
                    k--;
                }
            }
        }
        int sum = 0;
        for(const auto &a:nums){
            sum += a;
        }
        return sum;
    }
};

> 贪心解法

class Solution {
static bool cmp(int a, int b) {
    return abs(a) > abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(), A.end(), cmp);       // 第一步
        for (int i = 0; i < A.size(); i++) { // 第二步
            if (A[i] < 0 && K > 0) {
                A[i] *= -1;
                K--;
            }
        }
        if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步
        int result = 0;
        for (int a : A) result += a;        // 第四步
        return result;
    }
};