1005.K次取反后最大化的数组和.md

1005.K次取反后最大化的数组和

原题

求负数个数minus，然后比较minus和k关系。有负则翻正，负数不够用则取绝对值最小的数翻转

1.若k < minus，则取最小的k个负数反转即可

2.否则负数不够用，先将所有负数（minus个）翻转

剩下k-minus次翻转操作，全部用在绝对值最小的数，这样对求最大和影响最小

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        mins = []
        n = len(nums)
        nums.sort() #先排序
        minus = 0   #负数个数
        minabsIdx = 0    #绝对值最小的数下标
        #遍历求负数个数和绝对值最小数下标
        for i in range(n):
            if nums[i] < 0:
                minus  += 1
            if abs(nums[i]) < abs(nums[minabsIdx]):
                minabsIdx = i
        
        #先将最小的负数全部变正
        for i in range(n):
            if i < min(k, minus):
                nums[i] = -nums[i]
        #若 k 比 负数 个数 还多，则取绝对值较小的数翻转
        if k > minus:
            for _ in range(k-minus):
                nums[minabsIdx] = -nums[minabsIdx]
        #最后求和
        cnt = 0
        for i in range(n):
            cnt += nums[i]
        return cnt