Maximize Array Sum after Exactly K Sign Changes
Company: Infosys
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
One operation selects an index and negates its value. Apply exactly k operations; the same index may be selected repeatedly. Return the greatest possible final sum.
```cpp
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k);
};
```
### Examples
**Example 1:**
```text
Input: nums = [-4,-1,2], k = 1
Output: 5
Explanation: Negating-4 gives[4,-1,2] with sum5, the largest one-operation improvement.
```
**Example 2:**
```text
Input: nums = [-2,0,3], k = 4
Output: 5
Explanation: Negate-2 once and negate0 three times. All four operations are used without reducing the resulting sum5.
```
### Constraints
- `1 <= nums.length <= 10^4`.
- `-100 <= nums[i] <= 100`.
- `1 <= k <= 10^4`.
### Contract considerations
The output is a sum, not an array or a flip sequence. Values are small enough that all final sums fit int.
```hint Read the boundary condition
After taking all profitable negative-to-positive changes, what effect can two flips of the same index have?
```
### Boundary reminders
The output is a sum, not an array or a flip sequence. Values are small enough that all final sums fit int.
Overview: Maximize Array Sum after Exactly K Sign Changes. One operation selects an index and negates its value.