Funcia
Lv.1greedysorting

Maximize Sum After K Negations

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Given an integer array nums and an integer k, you must perform exactly k operations, each replacing some nums[i] with -nums[i] (the same index may be chosen repeatedly). Return the maximum possible sum of the array afterwards.

Examples

numskresult
[4, 2, 3]15
[3, -1, 0, 2]36
[2, -3, -1, 5, -4]213

Example 2 — flip -1, then spend the remaining two flips on 0.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(nums: int[], k: int) → long

Constraints

  • 1≤1 \le nums.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le nums[i] ≤109\le 10^9
  • 1≤1 \le k ≤109\le 10^9
  • The answer may exceed the 32-bit range.

Expected complexity

Time
O(N log N)
Space
O(1)

Examples

numskExpected
[4,2,3]15
[3,-1,0,2]36
[2,-3,-1,5,-4]213

Hint

Hint

The best flip is always the smallest (most negative) value: sort, then turn negatives positive from the smallest up. Flipping the same element twice changes nothing, so any remaining flips only matter through their parity: if an odd number is left, spend it on the element with the smallest absolute value. Performing up to 10910^9 flips one by one exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251196 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4013verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.