给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
其中
1 <= nums.length <= 104
-100 <= nums[i] <= 100
1 <= k <= 104
例子
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。
输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
解题思路
题意稍微解释下, 给定个数组nums, 次数k, 将数组内任意元素, 做k次取反操作, 一个元素可取多次
找到k次完成之后数组各元素相加的最大和
- 现将数组正序排列
- 先顺序把
负数变正数- 如果k无剩余, 直接返回相加和
- 如果k有剩余, 判断
剩余k的奇偶性-
偶数:直接求和 -
奇数:找到最小做一次反转, 再求和
-
这里把负数变正, 应该很好理解, 稍微解释下剩余k为何奇偶判断
以 nums = [2,-3,-1,5,-4], k=10 和 k=11 举例:
先正序数组, 负数变正数 数组为 [1, 2, 3, 4, 5], 需要消耗3次, 此时全正数求和最大为15
全正数之后, 只针对最小数做剩余次数取反就行, 因为做其他都不会为最大
- [-1, 2, 3, 4, 5] 和为 13
- [1, 2, 3, 4, -5] 和为 5
那么
k=11
剩余8次, 偶数, 可对首值做偶数次取反结构不变
可做到正序数组不变, [1, 2, 3, 4, 5], 满足找到最大
k=10
剩余7次, 奇数, 那么我们把最小值取反即可 [-1, 2, 3, 4, 5], 满足找到最大
未翻译版
func largestSumAfterKNegations(_ nums: [Int], _ k: Int) -> Int {
var temp = nums.sorted(), kd = k
for i in 0..<temp.count {
if temp[i] > 0 { break }
temp[i] = -temp[i]
kd -= 1
if kd == 0 { break }
}
if kd > 0 && kd % 2 == 1 {
temp = temp.sorted()
temp[0] = -temp[0]
}
return temp.reduce(0,+)
}
翻译版
func largestSumAfterKNegations(_ nums: [Int], _ k: Int) -> Int {
// 定位temp为正序数组, 次数kd为 k
var temp = nums.sorted(), kd = k
// 遍历temp
for i in 0..<temp.count {
// 如果temp[i] 大于 0, 弹出循环
if temp[i] > 0 { break }
// 如果temp[i] 小于 0 取反
temp[i] = -temp[i]
// 次数-1
kd -= 1
// 如果没有次数了 弹出循环
if kd == 0 { break }
}
// 如果次数剩余, 并且剩余次数为奇数, 做最小值取反
if kd > 0 && kd % 2 == 1 {
temp = temp.sorted()
temp[0] = -temp[0]
}
// 数组元素求和返回结果
return temp.reduce(0,+)
}
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
网友评论