题目

leetcode:1005

代码与解析

原文链接：K次取反后最大化的数组和

一开始，我做的方法是每次都将数组排序，然后取最小值，取负值

时间复杂度太高

// 不推荐
func largestSumAfterKNegations(nums []int, k int) int {
    for i:=0;i<k;i++{
        sort.Ints(nums)
        nums[0] = -nums[0]
    }
    sum := 0
    for _, v := range nums{
        sum += v
    }
    return sum
}

然后看了题解，
第一。三步很巧

第一步保证了，数组在有负值，负值变正后的顺序
第三部减少了遍历次数，

func largestSumAfterKNegations(nums []int, k int) int{
    // 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
    sort.Slice(nums, func(i, j int)bool{
        return math.Abs(float64(nums[i]))>math.Abs(float64(nums[j]))
    })
    // 第二步：从前向后遍历，遇到负数将其变为正数，同时K--
    for i, _:= range nums{
        if nums[i]<0&&k>0{
            nums[i] = -nums[i]
            k--
        }
    }
    // 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
    // 这里有的大佬写的，if K%2 == 1 ，取余，如果余数奇数，那么就要变换一次
    for i:=0;i<k;i++{
        nums[len(nums)-1] = -nums[len(nums)-1]
    }
    // 求和
    res := 0
    for _,v := range nums{
        res += v
    }
    return res
}

if K%2 == 1 {
    nums[len(nums)-1] = -nums[len(nums)-1]
}

有大佬这样写，这样取余，看还需要变换符号次数