A dockyard control room tracks every container slot on an outbound barge as a signed integer on the shipment manifest: a positive value means cargo was loaded onto that slot, and a negative value means the slot is running ballast that drags the total down. The crane operator holds a remote trigger that flips the recorded sign of whichever slot it points at (multiplying that slot's value by -1), and dockyard policy requires the trigger to be fired exactly K times before the barge is cleared to leave port -- the same slot may be triggered more than once if that turns out to be useful. After all K triggers have been spent, report the largest possible total weight the manifest can show.
n and k.n integers a_1 ... a_n, the manifest's slot values.A single integer: the maximum possible sum of the manifest after exactly k sign-flip triggers have been applied in total (spread across the slots however is best, with repeats on the same slot allowed).
Example 1
Input
3 1 5 -2 3
Expected
10
Explanation
Only one trigger is allowed. The sole negative slot (-2) is the best target: flipping it gives +2, and the manifest total becomes 5 + 2 + 3 = 10.
Example 2
Input
4 3 -4 -2 1 3
Expected
8
Explanation
Two of the three triggers turn both negative slots positive: -4 becomes 4 and -2 becomes 2. The third trigger cannot be saved, so it is spent on the current smallest value (1), flipping it to -1 to minimize the loss. Total: 4 + 2 + (-1) + 3 = 8.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →