problem

1005. Maximize Sum Of Array After K Negations

题意

 

solution#1:

code

 

 

 

solution#2:

先循环k次，每次把最小值前加负号，然后遍历求和；

code

 

 

solution#3:

• 翻转，应尽可能的翻转负数，同时翻转两次是可以抵消的，故分为如下三种情况；
• 1、K小于负数的个数，翻转最小的K个负数；
• 2、K大于负数的个数，且K-负数的个数等于偶数，翻转所有负数；
• 3、K大于负数的个数，且K-负数的个数等于奇数，翻转所有负数；
• 对于1，2返回翻转之后数组的和，对于3，返回翻转之后数组的和减去数组中最小数字的两倍。

code

 

 

solution#4:

(优先队列) O(nlogn)O(nlogn)
根据题意，我们易知，只需将数组从小到大排序，那么，我们从前往后每次将最小的元素翻转，先把所有负数尽量翻转为正数，如果负数都翻转完毕还没有达到K次翻转，那么一直翻转绝对值最小的那个元素，直到满足K次翻转即可。这个过程我们可以用优先队列或最小堆实现。先把A数组建堆，那么每次从最小堆中弹出最小值，翻转之后再插入堆中，直到操作K次为止。

时间复杂度分析：建堆和翻转重新入堆复杂度均为O(nlogn)O(nlogn)，所以总时间复杂度为O(nlogn)O(nlogn)。

code

 

 

参考

1. leetcode_easy_greedy_1005. Maximize Sum Of Array After K Negations;

2. 1005.Maximize Sum Of Array After K Negations（K 次取反后最大化的数组和）;

3. Golang Leetcode 1005. Maximize Sum Of Array After K Negations.go;

4. LeetCode 1005. Maximize Sum Of Array After K Negations ;

5. std::min_element;

完