Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/1005.html
Given an array A of integers, we must modify the array in the following way: we choose an i and replace A[i] with -A[i], and we repeat this process K times in total. (We may choose the same index i multiple times.)
Return the largest possible sum of the array after modifying it in this way.
Example 1:
Input: A = [4,2,3], K = 1
Output: 5
Explanation: Choose indices (1,) and A becomes [4,-2,3].
Example 2:
Input: A = [3,-1,0,2], K = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].
Example 3:
Input: A = [2,-3,-1,5,-4], K = 2
Output: 13 Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].
Note:
1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100
Algorithm 1
This question gives an array of integers, which may be positive or negative, and then gives a positive integer K, saying that K operations can be performed, and each operation can flip the number at any position into its opposite number. That is, a positive number becomes a negative number, or a negative number becomes a positive number, and the number at the same position can be transformed multiple times. Now, after K transformations, the largest array sum is returned.
First, think about how to make the sum of the array the largest. It must be as many positive numbers as possible. If there are negative numbers in the array, it must be turned into a positive number. At this time, the size relationship between the number of negative numbers in the array and K is not Not sure, so we need to discuss it by situation. Of course, the simplest case is that the number of negative numbers is exactly equal to K, so as long as all negative numbers become positive numbers, it’s fine. If the number of negative numbers is greater than K, the smallest K must be selected, that is, the K with the largest absolute value, so that the sum can be maximized after the flip. If the number of negative numbers is less than K, they are all flipped into positive numbers at this time, but the K value has not been used up, and it is still necessary to flip. At this time, we need to divide the parity of K to discuss, because the same position can be flipped multiple times, if K is Even numbers can be flipped back after each flip without any impact. If K is an odd number, there must be a non-negative number that will be flipped. It is definitely hoped that the smallest non-negative number will be flipped, which will have the least impact on the result.
After analyzing this, basically the whole problem-solving idea is there. Use a priority queue to record the absolute value of all negative numbers, and use a variable mn to record the number with the smallest absolute value in the array. Traverse the array. If you encounter a negative number, Then put the corresponding positive number into the priority queue, and then add this number to the result res every time, and update the number with the smallest absolute value. After traversing, the number of traversal is the smaller value between the number of negative numbers and K. Each time the negative number with the largest absolute value is taken out, the absolute value is multiplied by 2 and added to the result res. After the loop is over, the value of K may be odd or even. When K is even (including 0), directly returns res. If it is odd, subtract 2 times mn, which is the smallest absolute value in the array. See the code as follows:
Code 1
C++
```cppclass Solution {
public:
int largestSumAfterKNegations(vector
# Algorithm 2
We can also not use the priority queue, but sort the array first, so that all the negative numbers are in front of the array, and then turn the first K negative numbers into positive numbers at this time, pay attention to only flip the negative numbers, if the number of negative numbers is less than K, it will not flip excess positive numbers.
Then traverse the array at this time, find the array, and find the smallest number in the array at this time. At this time, K still has two cases of odd and even. When K is even (including 0), directly return the sum of the array, if it is odd At this time, it means that the negative numbers in the array have all been flipped to positive numbers, then the smallest number is the number with the smallest absolute value, minus 2 times it, see the code as follows:
# Code 2
C++
```cppclass Solution {
public:
int largestSumAfterKNegations(vector<int>& A, int K) {
int res = 0, n = A.size(), mn = INT_MAX;
sort(A.begin(), A.end());
for (int i = 0; i < n && K > 0 && A[i] < 0; ++i, --K) {
A[i] = -A[i];
}
for (int num : A) {
res += num;
mn = min(mn, num);
}
return res - (K % 2) * 2 * mn;
}
};
-
class Solution { public int largestSumAfterKNegations(int[] A, int K) { Arrays.sort(A); int length = A.length; for (int i = 0; i < length && K > 0; i++) { if (A[i] < 0) { A[i] = -A[i]; K--; } else if (K % 2 != 0) { if (i == 0) A[i] = -A[i]; else { if (A[i - 1] <= A[i]) A[i - 1] = -A[i - 1]; else A[i] = -A[i]; } break; } } int sum = 0; for (int num : A) sum += num; return sum; } } ############ class Solution { public int largestSumAfterKNegations(int[] nums, int k) { Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) { cnt.merge(x, 1, Integer::sum); } for (int x = -100; x < 0 && k > 0; ++x) { if (cnt.getOrDefault(x, 0) > 0) { int m = Math.min(cnt.get(x), k); cnt.merge(x, -m, Integer::sum); cnt.merge(-x, m, Integer::sum); k -= m; } } if ((k & 1) == 1 && cnt.getOrDefault(0, 0) == 0) { for (int x = 1; x <= 100; ++x) { if (cnt.getOrDefault(x, 0) > 0) { cnt.merge(x, -1, Integer::sum); cnt.merge(-x, 1, Integer::sum); break; } } } int ans = 0; for (var e : cnt.entrySet()) { ans += e.getKey() * e.getValue(); } return ans; } } -
// OJ: https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/ // Time: O(NlogN) // Space: O(1) class Solution { public: int largestSumAfterKNegations(vector<int>& A, int K) { sort(begin(A), end(A)); int sum = 0, i = 0; for (; K > 0 && i < A.size() && A[i] < 0; ++i, --K) sum += -A[i]; if (K % 2 && (i == A.size() || A[i] != 0)) { if (i == 0) sum -= A[i]; else if (i == A.size()) sum += 2 * A[i - 1]; else if (-A[i - 1] < A[i]) sum += 2 * A[i - 1] + A[i]; else sum -= A[i]; ++i; } for (; i < A.size(); ++i) sum += A[i]; return sum; } }; -
class Solution: def largestSumAfterKNegations(self, nums: List[int], k: int) -> int: counter = Counter(nums) ans = sum(nums) for i in range(-100, 0): if counter[i]: ops = min(counter[i], k) ans -= i * ops * 2 counter[i] -= ops counter[-i] += ops k -= ops if k == 0: break if k > 0 and k % 2 == 1 and not counter[0]: for i in range(1, 101): if counter[i]: ans -= 2 * i break return ans ############ class Solution(object): def largestSumAfterKNegations(self, A, K): """ :type A: List[int] :type K: int :rtype: int """ _sum = sum(A) heapq.heapify(A) while K > 0: curmin = heapq.heappop(A) heapq.heappush(A, -curmin) K -= 1 _sum += -curmin * 2; return _sum -
func largestSumAfterKNegations(nums []int, k int) (ans int) { cnt := map[int]int{} for _, x := range nums { cnt[x]++ } for x := -100; x < 0 && k > 0; x++ { if cnt[x] > 0 { m := min(k, cnt[x]) cnt[x] -= m cnt[-x] += m k -= m } } if k&1 == 1 && cnt[0] == 0 { for x := 1; x <= 100; x++ { if cnt[x] > 0 { cnt[x]-- cnt[-x]++ break } } } for x, v := range cnt { ans += x * v } return } func min(a, b int) int { if a < b { return a } return b } -
function largestSumAfterKNegations(nums: number[], k: number): number { const cnt: Map<number, number> = new Map(); for (const x of nums) { cnt.set(x, (cnt.get(x) || 0) + 1); } for (let x = -100; x < 0 && k > 0; ++x) { if (cnt.get(x)! > 0) { const m = Math.min(cnt.get(x) || 0, k); cnt.set(x, (cnt.get(x) || 0) - m); cnt.set(-x, (cnt.get(-x) || 0) + m); k -= m; } } if ((k & 1) === 1 && (cnt.get(0) || 0) === 0) { for (let x = 1; x <= 100; ++x) { if (cnt.get(x)! > 0) { cnt.set(x, (cnt.get(x) || 0) - 1); cnt.set(-x, (cnt.get(-x) || 0) + 1); break; } } } let ans = 0; for (const [key, value] of cnt.entries()) { ans += key * value; } return ans; }