Best after k flips: hints, no solution
Medium · Greedy
A soil sensor logs one reading per plot, and some readings are negative. A correction pass flips the sign of exactly k different readings: a chosen reading x becomes -x, and no reading can be chosen twice. Choose which readings to flip so that the sum of all readings after the pass is as large as possible, and return that sum. You must flip exactly k readings even if that lowers the sum. The value k is never larger than the number of readings.
Examples
- Input
- readings = [4, -2, 7, -1, 3], k = 2
- Output
- 17
- Note
- Flip -2 and -1 to get 4 + 2 + 7 + 1 + 3.
- Input
- readings = [3, 1, 2], k = 3
- Output
- -6
- Note
- All three readings must be flipped.
- Input
- readings = [-5, 2, -3], k = 0
- Output
- -6
Constraints
- 0 <= readings.length <= 60000
- -100000 <= readings[i] <= 100000
- 0 <= k <= readings.length
Hint 1: a nudge
Flipping one reading changes the total by a fixed amount that depends only on that reading. What is that change, and which readings make it largest?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.