• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

开发技术 开发技术 4小时前 3次浏览

给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。)

以这种方式修改数组后,返回数组可能的最大和。

示例 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]。

提示:

1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations
参考:

python

# 1005.k次取反后最大化数组和

class Solution:
    def largestSumAfterKNegations(self, A: [int], K: int) -> int:
        """
        贪心算法:
        1.按绝对值,由大到小排序
        2.遍历数组,将值小于0的变正,K--
        3.遍历完数组,K依然大于0,考虑将数组最小值 *(-1)**K, 只改变最小值的正负
        4.求和
        :param A:
        :param K:
        :return:
        """
        A = sorted(A, key=abs, reverse=True)
        for i in range(len(A)):
            if K > 0 and A[i] < 0:
                A[i] *= -1
                K -= 1
        if K > 0:
            A[-1] *= (-1)**K
        return sum(A)

golang

package main

import (
	"fmt"
	"math"
	"sort"
)

func main()  {
	nums := []int{3,-1,0,2}
	fmt.Println(largestSumAfterKNegations(nums, 3))
}

func largestSumAfterKNegations(nums []int, K int) int {
	// 1.绝对值排序,从大到小
	sort.Slice(nums, func(i, j int) bool {
		return math.Abs(float64(nums[i])) > math.Abs(float64(nums[j]))
	})
	// 2.遍历数组,负的变正, K--
	for i:=0;i<len(nums);i++ {
		if K > 0 && nums[i] < 0 {
			nums[i] = -nums[i]
			K--
		}
	}
	// 3.遍历完上面数组,K依然大于0,通过改变数组最小值,
	//如果K==偶数,其实数组不变,否则奇数下,改变最小的数组元素,保持整体最优
	if K % 2 == 1 {
		nums[len(nums)-1] *= -1
	}
	// 4.求和
	res := 0
	for _, v := range nums {
		res += v
	}
	return res
}

程序员灯塔
转载请注明原文链接:1005-K 次取反后最大化的数组和
喜欢 (0)