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

力扣传送门(opens new window)

给定一个整数数组 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

解题思路：

这道题的解题思路是通过贪心算法来求解。

首先，我们可以观察到，将一个正数变为负数可以增加数组的和，而将一个负数变为正数可以减少数组的和。因此，我们应该优先选择负数进行修改，以尽可能增加数组的和。

具体的解题步骤如下：

1. 统计数组中的负数个数，记为negativeCount。
2. 如果 K 小于等于 negativeCount，那么我们可以将 K 个负数变为正数，从而增加数组的和。遍历数组，将前 K 个负数取相反数，然后返回数组的和即可。
3. 如果 K 大于 negativeCount，那么我们首先将所有负数变为正数，并将 K 减去 negativeCount。此时，数组中只剩下非负数。
4. 如果 K 的值为偶数，那么不需要再进行修改，直接返回数组的和即可。
5. 如果 K 的值为奇数，我们需要找到数组中的最小非负数，并将其变为负数，从而减少数组的和。最后返回数组的和。

代码实现：

public class Solution {
    public int largestSumAfterKNegations(int[] A, int K) {
        // 统计负数个数
        int negativeCount = 0;
        for (int num : A) {
            if (num < 0) {
                negativeCount++;
            }
        }
    
        // 如果 K 小于等于 negativeCount，将 K 个负数变为正数
        if (K <= negativeCount) {
            Arrays.sort(A);
            for (int i = 0; i < K; i++) {
                A[i] = -A[i];
            }
        } else {
            // 将所有负数变为正数
            for (int i = 0; i < A.length; i++) {
                A[i] = Math.abs(A[i]);
            }
        
            // 计算剩余需要修改的次数
            int remainingK = K - negativeCount;
        
            // 如果剩余次数为偶数，则不需要再修改
            if (remainingK % 2 == 0) {
                return sumArray(A);
            } else {
                // 找到数组中的最小非负数，并将其变为负数
                int minNum = Integer.MAX_VALUE;
                for (int num : A) {
                    minNum = Math.min(minNum, num);
                }
                for (int i = 0; i < A.length; i++) {
                    if (A[i] == minNum) {
                        A[i] = -A[i];
                        break;
                    }
                }
            }
        }
    
        return sumArray(A);
    }
  
    private int sumArray(int[] A) {
        int sum = 0;
        for (int num : A) {
            sum += num;
        }
        return sum;
    }
}