数据结构与算法之K次取反后最大化的数组和

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

力扣题目链接：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。)

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

示例 1：

• 输入：A = [4,2,3], K = 1
• 输出：5
• 解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。

示例 2：

• 输入：A = [3,-1,0,2], K = 3
• 输出：6
• 解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。

示例 3：

• 输入：A = [2,-3,-1,5,-4], K = 2
• 输出：13
• 解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。

提示：

• 1 <= A.length <= 10000
• 1 <= K <= 10000
• -100 <= A[i] <= 100

思路

本题思路其实比较好想了，如何可以让数组和最大呢?

贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

局部最优可以推出全局最优。

那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。

那么又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值可以达到最大(例如正整数数组{5, 3, 1}，反转1 得到-1 比 反转5得到的-5 大多了)，全局最优：整个 数组和 达到最大。

虽然这道题目大家做的时候，可能都不会去想什么贪心算法，一鼓作气，就AC了。

我这里其实是为了给大家展现出来 经常被大家忽略的贪心思路，这么一道简单题，就用了两次贪心!

那么本题的解题步骤为：

• 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
• 第二步：从前向后遍历，遇到负数将其变为正数，同时K--
• 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
• 第四步：求和

对应C++代码如下：

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; 
    } 
}; 

总结

贪心的题目如果简单起来，会让人简单到开始怀疑：本来不就应该这么做么?这也算是算法?我认为这不是贪心?

本题其实很简单，不会贪心算法的同学都可以做出来，但是我还是全程用贪心的思路来讲解。

因为贪心的思考方式一定要有!

如果没有贪心的思考方式(局部最优，全局最优)，很容易陷入贪心简单题凭感觉做，贪心难题直接不会做，其实这样就锻炼不了贪心的思考方式了。

所以明知道是贪心简单题，也要靠贪心的思考方式来解题，这样对培养解题感觉很有帮助。

其他语言版本

Java

class Solution { 
    public int largestSumAfterKNegations(int[] nums, int K) { 
     // 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小 
 nums = IntStream.of(nums) 
       .boxed() 
       .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)) 
       .mapToInt(Integer::intValue).toArray(); 
 int len = nums.length; 
 for (int i = 0; i < len; i++) { 
     //从前向后遍历，遇到负数将其变为正数，同时K-- 
     if (nums[i] < 0 && K > 0) { 
      nums[i] = -nums[i]; 
      K--; 
     } 
 } 
 // 如果K还大于0，那么反复转变数值最小的元素，将K用完 
 
 if (K % 2 == 1) nums[len - 1] = -nums[len - 1]; 
 return Arrays.stream(nums).sum(); 
 
    } 
} 

class Solution { 
    public int largestSumAfterKNegations(int[] A, int K) { 
        if (A.length == 1) return k % 2 == 0 ? A[0] : -A[0]; 
        Arrays.sort(A); 
        int sum = 0; 
        int idx = 0; 
        for (int i = 0; i < K; i++) { 
            if (i < A.length - 1 && A[idx] < 0) { 
                A[idx] = -A[idx]; 
                if (A[idx] >= Math.abs(A[idx + 1])) idx++; 
                continue; 
            } 
            A[idx] = -A[idx]; 
        } 
 
        for (int i = 0; i < A.length; i++) { 
            sum += A[i]; 
        } 
        return sum; 
    } 
} 

Python

class Solution: 
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int: 
        A = sorted(A, key=abs, reverse=True) # 将A按绝对值从大到小排列 
        for i in range(len(A)): 
            if K > 0 and A[i] < 0: 
                A[i] *= -1 
                K -= 1 
        if K > 0: 
            A[-1] *= (-1)**K #取A最后一个数只需要写-1 
        return sum(A) 

Go

func largestSumAfterKNegations(nums []int, K int) int { 
 sort.Slice(nums, func(i, j int) bool { 
  return math.Abs(float64(nums[i])) > math.Abs(float64(nums[j])) 
 }) 
 
 for i := 0; i < len(nums); i++ { 
  if K > 0 && nums[i] < 0 { 
   nums[i] = -nums[i] 
   K-- 
  } 
 } 
 
 if K%2 == 1 { 
  nums[len(nums)-1] = -nums[len(nums)-1] 
 } 
 
 result := 0 
 for i := 0; i < len(nums); i++ { 
  result += nums[i] 
 } 
 return result 
} 

Javascript

var largestSumAfterKNegations = function(nums, k) { 
    nums.sort((a, b) => { 
        return Math.abs(b) - Math.abs(a) 
    }) 
    for(let i = 0; i < nums.length; i++) { 
        if(nums[i] < 0 && k > 0) { 
            nums[i] *= -1 
            k-- 
        } 
    } 
 
    if(k > 0 && k % 2 === 1) { 
        nums[nums.length - 1] *= -1 
    } 
    k = 0 
 
    return nums.reduce((a, b) => { 
        return a + b 
    }) 
};