Maximize Sum Of Array After K Negations - Practice Coding Problems

Maximize Sum Of Array After K Negations - Problem

Given an integer array nums and an integer k, modify the array in the following way: choose an index i and replace nums[i] with -nums[i].

You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,2,3], k = 1

› Output: 5

💡 Note: Choose index 1 and nums becomes [4,-2,3]. Sum is 4 + (-2) + 3 = 5, which is the maximum possible.

Example 2 — Multiple Negations

$ Input: nums = [3,-1,0,2], k = 3

› Output: 6

💡 Note: Choose indices (1, 2, 2) and nums becomes [3,1,0,2]. Sum is 3 + 1 + 0 + 2 = 6.

Example 3 — All Negative

$ Input: nums = [-1,-2,-3], k = 2

› Output: 4

💡 Note: Flip the two most negative: [-1,-2,-3] → [-1,-2,3] → [-1,2,3]. Sum is -1 + 2 + 3 = 4.

Constraints

1 ≤ nums.length ≤ 10⁴
-100 ≤ nums[i] ≤ 100
1 ≤ k ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array [4,2,3] with k=1 operations allowed

Process

Choose optimal element to negate for maximum sum

Output

Maximum possible sum after k negations

Key Takeaway

🎯 Key Insight: Always flip the most negative numbers first, or if all positive, flip the smallest to minimize loss

Asked in

G Google 15 a Amazon 12

The key insight is to greedily flip the most negative numbers first to maximize the sum gain. The greedy approach sorts the array and flips negatives, then handles remaining operations optimally. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(n^k)	O(k)	Try all possible ways to apply k negations and pick the maximum sum
Greedy Approach	O(n log n)	O(1)	Sort array and greedily flip the most negative numbers first

Brute Force - Try All Combinations — Algorithm Steps

Generate all ways to choose k positions (with repetition)
For each combination, apply negations and calculate sum
Return the maximum sum found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Try all ways to apply k negations

Calculate Sums

Compute sum for each combination

Find Maximum

Return the highest sum found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int maxSum = INT_MIN;

void backtrack(int* arr, int n, int operationsLeft) {
    if (operationsLeft == 0) {
        int sum = 0;
        for (int i = 0; i < n; i++) sum += arr[i];
        if (sum > maxSum) maxSum = sum;
        return;
    }
    
    for (int i = 0; i < n; i++) {
        arr[i] = -arr[i];
        backtrack(arr, n, operationsLeft - 1);
        arr[i] = -arr[i]; // backtrack
    }
}

int solution(int* nums, int n, int k) {
    maxSum = INT_MIN;
    int* arr = malloc(n * sizeof(int));
    memcpy(arr, nums, n * sizeof(int));
    backtrack(arr, n, k);
    free(arr);
    return maxSum;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100], n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    printf("%d\n", solution(nums, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^k)

For each of k operations, we can choose any of n positions, leading to n^k combinations

✓ Linear Growth

Space Complexity

O(k)

Recursion stack depth of k for generating combinations

✓ Linear Space

28.3K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler