LeetCode 1005. Maximize Sum Of Array After K Negations

问题

问题描述：给定一个整形数组 A，可以通过以下方式修改它：选择 i，将其反转 A[i] = -A[i]，重复 K 次，可以选择相同的i反转多次。要求返回反转之后的最大和。

栗子1：

输入：A = [4, 2, 3], K = 1
输出：5
A 变为 [4, -2, 3]

栗子2：

输入： A = [3, -1, 0, 2], K = 3
输出：6
A 变为 [3, 1, 0, 2]

栗子3：

输入：A = [2, -3, -1, 5, -4], K = 2
输出：13
A 变为 [2, 3, -1, 5, 4]

注意：

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

想看英文的戳这里：原题地址

解题思路

首先有一个很重要的点是，如果对一个数进行偶数次的反转，它的值保持不变。

我的解法

为了让和最大，如果有负数，需要尽量让负数进行反转，减少正数的反转。所以会分为以下几种情况来考虑：

无负数，全为正数

如果 K 为偶数，那么可以保持不变，最大值就是原先数组的和。因为可以对第一个数一直反转，反转 2 次就保持原值了。

比如 A = [4,3,2]，K = 2，那么我们可以对 4 进行 2 次反转，结果不变。
如果 K 为奇数，那么肯定有一个数需要变为负数。我们需要选择最小的数反转为负数，才能保证最大值。

比如 A = [4,3,2]，K = 1，那么我们可以对最小数 2 进行 1 次反转，变成[4,3,-2]。
比如 K = 5，偶数次的都可以忽略，因为对值无影响，所以我们最终计算的只是5 % 2 = 1次的反转，与上面分析一样。

有负数，有正数

在这种情况下，需要考虑K与负数个数negCount问题。

K <= negCount

如果 K <= negCount，那么很简单，排序后，只需要把前K个负数进行反转即可。
比如A = [2,-3,-1,5,-4]，K = 2，反转最小的 2 个负数即可，A 变成[2,3,-1,5,4]。

K > negCount

如果K > negCount，我们可以考虑将负数先全部反转，但是可能会涉及到反转正数的问题。

如果 k - negCount 为偶数，那么剩余的次数落在正数头上。由于是2的倍数次反转，刚好可以抵消，正数保持不变。

比如A = [2,-3,-1,5,-4]，K = 5，由于负数有 3 个，那么刚好还剩 2 次反转，抵消，正数保持不变。
如果k - negCount为奇数，则需要考虑是反转正数，还是将负数保持不变（即多余的1次落到负数头上）。

这里需要考虑到负数的最大值与正数的最小值绝对值大小问题。

如果负数的绝对值大，那么反转正数。比如A = [2,-6,-4,5,-8]，K = 4，那么 A = [-2,6,4,5,8]。

如果正数的绝对值大，那么负数保持不变。比如A = [2,-3,-1,5,-4]，K = 4，那么 A = [2,3,-1,5,4]。

代码如下：

// 53.66%
func largestSumAfterKNegations(_ A: [Int], _ K: Int) -> Int {
    // 存负数
    var negArray = [Int]()
    
    // 存正数
    var posArray = [Int]()
    var sum = 0
    
    for a in A {
        sum += a
        
        if a <= 0 {
            negArray.append(a)
        } else {
            posArray.append(a)
        }
    }
    
    // 排序
    negArray = negArray.sorted()
    posArray = posArray.sorted()
    
    // 需要考虑无负数的情况
    if negArray.count == 0, posArray.count > 0 {
        // 反转 2 次，抵消
        if K % 2 == 0 {
            return sum
        } else {
            return sum - 2 * posArray[0]
        }
    } else {
        // 如果 K 大于负数的个数，就需要到处理正数，优先把正数反转 2 次，即保持不变
        if K > negArray.count {
            let leftCount = K - negArray.count
            
            // count 表示需要反转负数的个数
            var count = negArray.count
            
            // 奇数，需要比较正数的最小值与负数的最大值的绝对值关系，如果是偶数，可以对负数全部操作。
            if leftCount % 2 == 1 {
                // 如果负数的绝对值小，则最后一个负数保持不变，相当于 2 次反转。
                if posArray.count > 0 {
                    if -negArray.last! < posArray[0] {
                        count -= 1
                    } else {
                        // 负数反转的增益大于正数变负数，将正数转为负数
                        sum -= 2 * posArray[0]
                    }
                } else {
                    count -= 1
                }
            }
            
            // 反转负数
            var i = 0
            while i < count {
                sum -= 2 * negArray[i]
                i += 1
            }
        } else {
            // 负数变正数
            var i = 0
            while i < K {
                sum -= 2 * negArray[i]
                i += 1
            }
        }
    }
    
    return sum
}

更简洁的解法

思路跟上面的差不多，但是没有分那么多种情况，是一个比较完整的思路。

先对整个数组进行排序，将前 K 个负数反转，最后需区分剩下的次数是奇数还是偶数。
如果是偶数，则无影响，如果是奇数，则需要减去最小值*2。

// 60.98%
func largestSumAfterKNegations(_ A: [Int], _ K: Int) -> Int {
    // 先排序
    var sortedA = A.sorted()

    // 对前面的负数进行反转
    var i = 0
    var j = 0

    // 如果 K 大于负数的个数，最后需要判断是对哪个数进行反转
    while j < K, i < sortedA.count, sortedA[i] < 0 {
        sortedA[i] = -sortedA[i]
        j += 1
        i += 1
    }
    
    var sum = 0
    var k = 0

    // 记录最小的数
    var minNum = Int.max

    while k < sortedA.count {
        sum += sortedA[k]

        if sortedA[k] < minNum {
            minNum = sortedA[k]
        }

        k += 1
    }

    // 如果剩余的 K - j 是奇数，则需要减去 2*最小的数
    if (K - j) % 2 == 1 {
        sum -= 2 * minNum
    }

    return sum
}

LeetCode 1005. Maximize Sum Of Array After K Negations