# Maximize Sum Of Array After K Negations: Interview Notes
Maximize Sum Of Array After K Negations shows up often in coding rounds. Here is how I talk through it when the interviewer is watching.
## Key idea
You may flip the sign of any element k times (you can flip the same one more than once). Sort, flip the smallest (most negative) values first; if k remains and is odd, flip the current minimum absolute value once more. The sum after those flips is the answer.
## Steps to say out loud
1. Restate the input and the exact ask, and nail down constraints and overflow.
2. Name the pattern (binary search on the answer, monotonic stack or deque, interval / interval-DP, string hashing, graph traversal, or shortest paths) and why a nested scan or naive search fails.
3. Code it, then trace a short example plus one empty or already-solved edge case.
## Complexity
O(n log n).
## Common mistake
Flipping the largest positives first, or leaving an odd leftover k unused (you must spend it, and it should hit the smallest absolute value).
## Practice tip
Time yourself: two minutes to explain, ten to code, three to test edges. Disclosure: I work on Linkjob AI. I also keep a practice cheat sheet at AI interview assistant.