贪心-K次取反后最大化的数组和

方法一：暴力

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int sum = 0;
        int t;   //记录每次被翻转的下标
        int Max = INT_MIN;
        //先求和
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        for (int j = 1; j <= k; j++) {
            int temp = sum;
            Max = INT_MIN;
            for (int i = 0; i < nums.size(); i++) {
                temp = sum - 2 * nums[i];
                Max = max(temp, Max);
                if (Max == temp) {
                    t = i;
                }
            }
            sum = sum - 2 * nums[t];
            nums[t] = -nums[t];
        }
        return sum;
    }
};

 思路：

局部最优：每次遍历所有数组求出只翻转一个数所产生的最大值。

整体最优：K次翻转产生最大值。

所需要注意的是每次翻转的时候不要忘记对Max和temp进行初始化，还有记录所翻转的值。

方法二：贪心

class Solution {
static bool cmp(int a, int b) {
    return abs(a) > abs(b);
} 
 
public:
    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--;
            }
        }
        if (k % 2 == 1) {
            nums[nums.size() - 1] *= -1;
        }
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            res += nums[i];
        }
        return res;
    }
};

思路：两次不同情况的贪心

先进行排序，将绝对值大的放前面，绝对值小的放后面

第一次贪心：如果数组中有负数，则将绝对值大的负数先翻转过来，产生局部最大值。

第二次贪心，如果数组中没有负数了，就将绝对值最小的整数翻转过来，产生局部最大值。

注意：后面的if语句的条件是k%2，因为如果是偶数，翻转最后一个数两次相当于没有翻转，所以可以不管，如果是奇数，则只需要翻转一次。