這是悅樂(lè)書(shū)的第376次更新，第403篇原創(chuàng)

01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級(jí)別的第237題（順位題號(hào)是1005）。給定一個(gè)整數(shù)數(shù)組A，我們必須按以下方式修改數(shù)組：我們選擇一個(gè)i并用-A[i]替換A[i]，重復(fù)這個(gè)過(guò)程K次。（我們可以多次選擇相同的索引。）
以這種方式修改后，返回?cái)?shù)組可能的最大總和。例如：

輸入：A = [4,2,3], K = 1
輸出：5
說(shuō)明：選擇索引(1,)，A變?yōu)?code>[4,-2,3]。

輸入：A = [3,-1,0,2], K = 3
輸出：6
說(shuō)明：選擇索引(1, 2, 2)，A變?yōu)?code>[3,1,0,2]。

輸入：A = [2,-3,-1,5,-4], K = 2
輸出：13
說(shuō)明：選擇索引(1, 4)，A變?yōu)?code>[2,3,-1,5,4]。

注意：

• 1 <= A.length <= 10000

• 1 <= K <= 10000

• -100 <= A[i] <= 100
  
  

02 第一種解法

題目的意思是將A中的數(shù)進(jìn)行取反（正變負(fù)，負(fù)變正）K次，可以重復(fù)對(duì)一個(gè)元素取反，最后求A中元素總和的最大值。取反可以分為兩種情況：

當(dāng)A中都是正數(shù)的時(shí)候，比如{1,2,4,6}，如果K是偶數(shù)，那么可以不用進(jìn)行取反操作，因?yàn)樨?fù)負(fù)得正；如果K是奇數(shù)，則只需要對(duì)最小的數(shù)取反一次即可。

當(dāng)A中有正數(shù)也有負(fù)數(shù)的時(shí)候，比如{-4,-3,-1,2,5}，此時(shí)對(duì)負(fù)數(shù)元素進(jìn)行取反操作，直到當(dāng)前元素大于0或者K次轉(zhuǎn)換已用完，此時(shí)針對(duì)K中剩余的轉(zhuǎn)換次數(shù)，又可以細(xì)分為兩種情況：

（1）K中剩余的轉(zhuǎn)換次數(shù)為偶數(shù)，即A中元素全是正數(shù)，依據(jù)負(fù)負(fù)得正，不用再進(jìn)行額外的轉(zhuǎn)換了。

（2）K中剩余的轉(zhuǎn)換次數(shù)為奇數(shù)，即還需要再將某個(gè)元素轉(zhuǎn)換一次，而為了元素總和最大，需要比較當(dāng)前元素（正數(shù)）和前一個(gè)元素（負(fù)數(shù)）的絕對(duì)值大小，對(duì)較小的元素進(jìn)行取反。

最后使用一個(gè)for循環(huán)，計(jì)算A中所有元素總和。

public int largestSumAfterKNegations(int[] A, int K) {
    int sum = 0;
    Arrays.sort(A);
    if (A[0] >= 0) {
        if (K%2 != 0) {
            A[0] = -A[0];
        }
    } else {
        int i = 0;
        while (A[i] <= 0 && K > 0) {
            A[i] = -A[i];
            i++;
            K--;
        }
        // K中剩余有轉(zhuǎn)換次數(shù)且為奇數(shù)
        if (K > 0 && K%2 != 0) {
            // 取較小的元素進(jìn)行取反
            if (Math.abs(A[i]) < Math.abs(A[i-1])) {
                A[i] = -A[i];
            } else {
                A[i-1] = -A[i-1];
            }
        }
    }
    // 求和
    for (int num : A) {
        sum += num;
    }
    return sum;
}

03 第二種解法

思路和第一種解法類似，只是在處理K中剩余的轉(zhuǎn)換次數(shù)為奇數(shù)這個(gè)問(wèn)題上做了下優(yōu)化，在第一種解法中，我們是比較最后一次轉(zhuǎn)換的負(fù)數(shù)和它前一個(gè)正數(shù)的大小，換種角度理解，這兩個(gè)數(shù)已經(jīng)處于所有元素中的底部了，就像一個(gè)U型曲線的底一樣，而為了元素總和最大，需要將較小的值取反，即找出所有元素中的最小值即可。

先對(duì)A排序，利用循環(huán)，將前面的負(fù)數(shù)進(jìn)行轉(zhuǎn)換，順便計(jì)算元素總和并找出最小元素，如果A中負(fù)數(shù)已全部轉(zhuǎn)換完成（A中已不包含負(fù)數(shù)），且K中還有剩余的轉(zhuǎn)換次數(shù)，并且剩余的轉(zhuǎn)換次數(shù)為奇數(shù)，則將最小的正數(shù)減去兩次，因?yàn)?code>sum是全部元素的和，且全部元素都是正數(shù)，對(duì)最小的元素取反后變?yōu)樨?fù)數(shù)，則sum需要減兩次最小元素。例如{1,2,3}的和為6，對(duì)1取反后變?yōu)?code>{-1,2,3}，其和為4。

public int largestSumAfterKNegations2(int[] A, int K) {
    Arrays.sort(A);
    int sum = 0, min = Integer.MAX_VALUE;
    for (int num : A) {
        if (num <= 0 && K > 0) {
            num = -num;
            K--;
        }
        sum += num;
        min = Math.min(min, num);
    }
    // K中有剩余轉(zhuǎn)換次數(shù)且為奇數(shù)
    if (K > 0 && K%2 != 0) {
        // 減去2次最小值
        sum -= min*2;
    }
    return sum;
}

04 小結(jié)

算法專題目前已連續(xù)日更超過(guò)七個(gè)月，算法題文章242+篇，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

以上就是全部?jī)?nèi)容，如果大家有什么好的解法思路、建議或者其他問(wèn)題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持！