前往
大廳
主題

LeetCode - 1005. Maximize Sum Of Array After K Negations 解題心得

Not In My Back Yard | 2021-03-06 00:00:13 | 巴幣 0 | 人氣 194

題目連結:


題目意譯:
給定一整數陣列 A ,我們必須藉由以下方式修改該陣列:我們選擇一個 i 值然後將 A[i] 之值變為 -A[i],而我們總共會重複此步驟 K 次。(我們可以多次選擇同樣的索引值 i)

回傳在修改陣列後,最大可能的總和之值。

注:
1 ≦ A.length ≦ 10000
1 ≦ K ≦ 10000
-100 ≦ A[i] ≦ 100



範例測資:
範例 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]。


解題思維:
先由小到大排序陣列 A 裡面的數字,這麼做後負數(如果有的話)就會排在陣列前面。

假設負數有 M 個,如果 M ≧ K ,則產生最大總和的方式就是將前 K 個負數變為正數(因為有排序,所以排較前面的負得越多,所以轉正數時會越大);如果 M < K ,則將 M 個負數都先轉為正數,剩下的 K - M 次操作皆用在轉換完後最接近 0 的數字(這樣便可以確保其他大的數字不會變為負)。

根據上面的策略將數字轉換完後,將數字加總即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作