🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1005. Maximize Sum Of Array After K Negations
Сложность: easy
Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом.
Пример:
Input: nums = [4,2,3], k = 1
Output: 5
👨💻 Алгоритм:
1⃣Сортировка массива:
Отсортируйте массив nums по возрастанию, чтобы наибольшее количество раз менять самые маленькие (отрицательные) значения на их противоположные.
2⃣Модификация массива:
Пройдитесь по отсортированному массиву и замените k наименьших значений на их противоположные (умножьте на -1). Если встретите 0, прекратите дальнейшие изменения, так как изменение 0 на -0 не имеет смысла.
3⃣Проверка остатка изменений:
Если после первого прохода остались изменения (k нечетное), то найдите минимальное значение в измененном массиве и еще раз поменяйте его знак. Это обеспечит максимальную сумму.
😎 Решение:
class Solution {
fun largestSumAfterKNegations(nums: IntArray, k: Int): Int {
nums.sort()
var k = k
for (i in nums.indices) {
if (k > 0 && nums[i] < 0) {
nums[i] = -nums[i]
k--
}
}
if (k % 2 == 1) {
nums.sort()
nums[0] = -nums[0]
}
return nums.sum()
}
}
Ставь 👍 и забирай 📚 Базу знаний
